There are only a few bus companies that have a direct bus all the way from Nairobi to Malindi. Spider, Mash, and another company whos name I've forgotten all leave Nairobi from a similar area of town at the crossroads of Accra and River roads.
If it was up to me I would go with Mash but I guess they would be a tad more expensive than the other two coach firms.
Boarding a tut-tuk is definitely the easiest way of getting around Malindi, especially if you have just arrived at the bus park as the bus park is not exactly in the centre of town.
You won’t have to look for one as they are always on the look out for you; Malindi is positively infested with tuk-tuks. Trips within the centre of town should cost you no more than 50 bob.
If you intend to travel to Malindi by public means you can catch a bus from the bus park just before the Nyali bridge in the area of Mombasa called Buxton. Up untill December 2008 buses and matatus used to depart from in front of the New Peoples Hotel in Bondeni nearer the town centre. Buxton Bus park is also the place to catch a bus to Kilifi, Lamu, or Garissa.
There are both buses and matatus, for some reason the Mombasa to Malindi matatus are localy called "Saa robo" I don't know why coz it takes longer than 1/4 of an hour to get to Malindi, usually 2 hours.
Walking is the most common way of "transprtation" in Kenya, everywhere I was lots of people were out on the roads. There exists local bus service, besides matatu, but not that frequent as in Europe. Locals are used on walkings even if distances between places not short at all. Is it the reason why I couldn't see any overweight women or men, in fact, most of Kenyans are slim or slender in shape.
Matatus, the local variation of shared minibuses are actually much cheaper - but I must say I decided against: they were more than overcrowded - usually with a couple of people standing on the open door and gripping firmly on the roof. let's say they did not look neither comfortable nor safe, especially because of the high speed. There are plenty of taxis around - but they are geared towars foreigners - hence the prices aren't as low as you would expect - not even after bargaining - but if you can share it, it's not too bad. As a rule of thumb, however, the prive listed for a one way trip, can easily become the one for a return trip, including waiting time. No comment about the state of the cars: they are rustying away and are falling apart - at one point we drove into a mud pool and water entered the car from the bottom - leaving us laughing and with wet feet.