I'm sorry, I can't help with this one, and if I'd gone to Malaga 2 weeks ago instead of lying on the beach, who knows, maybe I could have been helpful and I really must make the effort in September, it's been too long since I was last there.
The best way to get to Gibraltar from Malaga would be on an excursion operated by a private company, but I don't think there are many such companies in Malaga because most people go to Malaga to see Malaga, and most of the companies tend to operate from Torremolinos and beyond.
The other alternative would be by bus from Malaga bus station, the journey takes 3 hours to La LÃÂÂnea de la Concepción, and then you walk across the border"¦.a bit of a nightmare stopping at places along the way.
http://www.ctsa-portillo.es/ima/pdf/la-linea.pdf?1
I would recommend that you treat them to this book to take with them, I have no vested interest in recommending this book, it's just a really good book when walking around Malaga to get the 'best' out of the city, and you can view some sample pages.
http://www.guide-to-malaga.co.uk/index.html
I'm never quite sure when someone says they're a vegetarian whether they don't eat meat or meat and fish, but if your Dad does eat fish, then he'll have no problem finding something to eat from the humble sardine, with every kind of fish in between to the lobster, you can get a vegetarian Paella these days.
The Spanish word for vegetarian is quite similar to English (Vegetariano (male) female Vegetariana.) and I feel confident that he'll not just be having ordinary meals, minus the meat.
HTH's
Sanji