You could take https://www.gibraltarshuttle.com/ direct from Midtown, Gibraltar to Malaga Airport, for £70 return. This service is twice a day. It is advisable to book. From Malaga airport you can get buses or a train into Malaga.
There is a bus from La Linea bus station to Malaga on Monday to Saturday, four times a day - three of those buses stop at three towns on the way (I'm not sure about the fourth bus operated by a different company). On Sunday there are five buses - four of which make the same three stops. That costs from €13.59 (one way) and takes 3 hours.
Or there is a more direct ("semidirecto") bus twice a day Monday to Friday, once a day on Saturdays and Sundays. This costs from €16.72 (one way) and takes 2 hrs 15mins.
Timetable ("horarios"): http://malaga.avanzagrupo.com/archivos/files/Horarios%202020/0120_enero/Horario%20autobuses%20La%20L%C3%ADnea_.pdf
I'd be inclined to book because it is infrequent even though it might not be busy outside the typical holiday periods. But at this time of year you can probably get a ticket at the bus station.
Select Cadiz, then Est. La Linea, then Malaga (Todos las paradas).
Thousands of people walk across the Gibraltar-Spain border a day but significant delays are rare, particularly outside Monday to Friday rush hours entering Gibraltar (8:30am to 9:30am) or entering Spain (5:00pm to 6:30pm). That is, you shouldn't have any difficulty leaving Gibraltar for the 9am bus from La Linea. If you have a machine readable passport you should not be delayed at all unless there is a queue entering Gibraltar at the Gibraltar side of the border (Spain has passport machines but Gibraltar does not). But if there are few other pedestrians it is quicker to walk past the border guard than use the machine.