mibuokami on 15 March 2011
Heroes of Might and Magic 3, meets all your criteria, cheap to get (use gog.com!) and easily the best heroes of the entire series.
You can also give Master of Orion I & II a try... if fact just go to www.gog.com and have a look at their selection, almost all games are classic hits that have been tested to work on newer OS, they're usually very cheap and have no DRM. An a lot of the games in their library meet your criteria.
