Alternative option, if horse is too slow, would be to become werewolf.
Werewolfs are significantly faster then horse. I preformed test to prove or bust this (unfortunatetly, I don't know how to capture screenshot in Skyrim). I started at Helgen and followed the road to Ivarstead. On horse, after 2 and half minute (duration of werewolf form) I passed the mountain and get to the "spring area" just when stopwatch hit 2:30. While in werewolf form, I hit that area around 2:10 (few seconds more or less). I believe I had time to come to Ivarstead, however, I didn't because humans are hostile while you are in wolf form. Instead, I went east towards Riften. All in all, I would say I travelled about 20% more in werewolf form. Also one thing which I noted - werewolf has way way more stamina then horse and he is freak of nature when comes to regenerating it.
Also, about your wolf problem - while in werewolf form they are friendly to you. However, note that your "wolf problem" is suddenly called "human problem". While in wolf form, you are attacked by other people in Skyrim (on horse 1 encounter with wolfs, in wolf form 2 encounters with humans - however, werewolf easly (and by this I mean realy easy) can outrun them).
The Elder Scroll Wiki says that werewolf form adds 100 stamina to you. I'm not sure about horses, but this means that wolf form sprinting time scales with your stamina (which is great if you're warrior or rogue). Just to note, I have 140 stamina while in human form.
The greatest disadvatage while you are in wolf form (if we are talking about travelling) is the fact you can't open your map, so it also depends can you remember the route by heart. I personally use this form to fast travel on the road to undiscovered areas / towns. Little tip - just rest for 24 hours if beast form fades and you still have long route ahead.
And in the end, like every true power user would say - it's 100% open source (== 0 money spent on wolf form if used for personal needs only).
P.S. Please do note that werewolf form has it's advantages and disadvantages and that you can only be in beast form for 2.5 min without feeding (not an option if you are travelling). Also, if you become werewolf, you can not become vampire (yeah, it sucks you can't be -"half vampite, half lycan, stronger then both*) To see if it suited for your playstyle follow the upper link.
Right, enough about werewolfs.
There is one horse in Skyrim which "is more then just a horse". It's Shadowmere. However, unlike in Oblivion, here she is NOT faster then other horses, don't be fooled by lore. The advantage of having Shadowmere is she can fight along your side and it's considered immortal (wolf problem - gone). Oh, yeah, according to wiki, she can go where none has gone before (she can climb where you couldn't normally).