The unicorn, a 4 RHD magical beast already touched upon back when tritons got reviewed. Of course, back there it was only present for one encounter per day, here things are quite different.
Unicorns have excellent stats for a 4 HD being, with huge bonuses to strength, constitution, charisma, and wisdom, a decent boost to dexterity (rare for something Large-sized), and no change to intelligence. Like horses, they're fast runners. Unlike horses, they enjoy natural armor on par with banded mail.
Unicorns lack hands (duh). They do get a pair of hoof attacks and a horn, though (which for some reason can all be used against the same creature).
Furthermore, the horned horses have various special abilities. Immunity to poison, charm, and compulsion is generally useful. Wild Empathy is very nice given an unicorn's huge racial bonus and charisma modifier, and at those levels encounters with animals can still be a real threat.
Finally, the SLAs. We're off to a great start with a permanent Magic Circle Against Evil. Detect Evil at-will is neat and can ruin plots, especially as it can be used as a free action. CLW (3/day) and CMW (1/day) are getting a bit weak by this level, but hey, they're free and not completely useless. Neutralize Poison is quite useful as well. Last is Greater Teleport within 'the confines of [the unicorn's] home'. It'll probably end up not being that useful for a traveling adventurer, though.
I think a LA of +1 is appropriate here. MCAE is a very strong ability to have on all-day at low levels, and the ability scores are high, but the lack of hands and clear advancement opportunities hinder things somewhat.