When I level up I feel a surge of indecision.
That's exactly how it gets me, too. In the early stages it's not so bad (only another 100 dead looters before the next level-up ~D), but by the time you're needing 10000+ exp for the next level, you have to think a bit about where the skills are going - I often think "I need more strength for the better armour, but I also need to up my riding, I can't take enough prisoners, and my inventory is FULL already....."
I've seen some great suggestions in this thread though.
* More books would be good
* Extra "trainers" around the map (love the Khergit horseman idea ....) - I thought maybe to add a random element, some of the "travellers" you meet (and usually ignore

) in taverns might turn out to be "Zomborg the Master Swordsman" who can train you in 1H/2H weapons etc - I don't know, maybe a mega-hard arena match with him.... possibilities are endless.
* Quests with different rewards - so far we can get relations, cash, exp, renown - why not skill points or proficiencies too?
* I like the idea of medicinal herbs - maybe they only grow in one or two (random) villages? Great for a healing boost (but should maybe "go off" like beef does now).
* Skill boosts with experience like Triosta suggests - would be a good one - even if it was a "backward trade" - ie you reach say 300 proficiency with a bow, then backtrade say 50 pts of proficiency into 1 point of power draw