Well from what I can tell, you're looking for a cheap dark age game to start with, I think I've got just the thing.
http://valhalla.eaststreetgames.com/MyHome/It's called Valhalla, the rules are free and they're loose enough to be adapted to any setting without any major gunplay. (Seriously, I've been thinking of porting it over to Lord of the Rings.) I haven't had the chance to play a solid game yet, but the mechanics look really smooth and I can find nothing but good review from people that have actually played. You can start out with squares of paper/card with names writen on them to signify warriors. One of the cool features of this game is you write your roster online and the website works out the equipment and class impact on your stats, all you do is print off your roster and you're ready to go! It seems to lend itself to solo play fairly well too.
Hope this has proven helpful, and the best of luck to you!
-Jeff