Hi Fiona. No great urgency to book a meal out for Christmas Day. It's a low-key day as far as the Spaniards are concerned, though that can't be said of the 24th (Nochebuena), which is one of the most important meals of the year for a Spanish family.
The locals don't really celebrate until the Three Kings (Los Reyes) come on the sixth of January.
Although the 25th is still a fiesta day, with all banks and shops closed, there will be many restaurants open for business in Fuengirola's Fish Alley. May see you there!

We stayed in Benalmadena over xmas 2003. Very low key, you will see a few xmas trees lit up but no problems with a xmas meal. Look around though because some places will try and rip you off. We stayed at the Sol Aloya Playa and most places did a xmas dinner. Not the hotels, but the bars on the sea front. You will enjoy it and i did come home with a tan. :D. Like mosr people have said. The Spanish celabrate the 3 kings which is after Dec but you will be suprised of how many english peole are there for xmas. Enjoy yourself and stop worrying. Must admit those heated pools are like jumping in the bath LOVELY .Anna. xxx

Ive lived in spain 6 years now and speaking from experience ann i would recomend booking if its xmas dinner ur after, to avoid dissapointment and all that, at least if its booked its booked, i can send some resturant numbers ur way if u would like? and as tonyadams78 mentioned fish alley in fuengirola have loads of fantastic restaurants.