I know, but it still seems odd. Another way of accomplishing this is to put it at you can only have a certain number of henchmen at a particular fame level. You can only have 1 henchman at 50 fame. Fame doesn't go away when you train the henchman, but you also don't get to train any more than 1. At 100 fame you can train 2 henchmen. If one dies, then you can replace him with no extra cost, but you are still limited on henchmen. Even if you increase the amount of fame required at the moment.

I wouldn't mind a tavern type shop where you recruit minor heroes (henchmen) or scions for an instant fee. Say you are in a pinch you can recruit them for 50 - 100 gold (outside your build que), while Altar gets to build them and design their own, as well as this hiring ability.

As to the champion list, I just don't think there are enough designed champions at the moment, hence the reason why it doesn't seem random enough.

That is a great idea. If the shop or the tavern is replaced by a mercenary group who arrives at a particular fame level (1, 10, ...) and offers you either a champion, a magical item or a xp book it would be less gamey.

I also am not a fan of the current "choose one of these two heroes now" mechanic.   I would prefer a choice such as what Wizard1200 proposed where I can choose something related to my heroes be it an item, some special training to gain XP for one of my current heroes or an actual hero.  

I like the idea. Allowing us to see the complete list of champions from the beginning and allowing us to forgo purchasing champions with fame until we choose to is a good Idea.

However I would like the list of available champions to be by faction, kingdom/empire, and once a champion is purchased by any kingdom/empire it will be removed from the list so that no one else can purchase a duplicate. This also makes champions a finite resource. Once all the champions are purchased there simply won't be any more accept from quests. Thus you have the choice of buying as many low level champions as you can and leveling them up or increasing your fame as fast as you can in order to get a few higher level champions. This will also fix the ability that is supposed to let you purchase empire and kingdom champions.

I also agree with the suggestion that fame could also be used to help purchase equipment thus giving you yet another option of only purchasing a couple of low level champions and then spending the rest of your fame on better equipment for your champions. The only thing that I would add to this would be for it to be a combination of fame and gildar when purchasing equipment rather than just fame.

I don't know if this has been done yet or not but please make sure that henchmen cost fame.

Last I also like the idea of using fame to instead boost nation wide growth. This will add yet another gameplay path of mostly forgoing champions in order to focus on more quickly growing your cities. I would suggest this be implemented through the building of special buildings witch require fame and a moderate amount of production.

Overall I believe that these suggestions would not only make the overall gameplay better but will also further diversify gameplay styles and gameplay goals. Do you focus on many champions, fewer champions, buying great equipment for your champions, increasing growth, or some middle ground between two or more of these options? This would also make AI gameplay styles and goals, thankfully, more varied and interesting. Finally the finite number of purchasable champions that can be purchased will push players to compete with other nations for them.

OK, I've revised my idea to:

Hero 1, Hero 2, wait for better Hero (next heroes you get will be higher lvl and start with a free lvl) , or Restoration potion.

Getting the choice of an item could be good. A tribute to how great you are. Balancing it may be hard? Having a couple 1 hero groups (+army ofc.) armed to the teeth questing for gear or particular better than average heroes. What would make it strong, I guess, is when you're attacking you could just combine them into a single even more powerful army, then go city cappin.

Though Win-Con related it could be interesting because you could gear your sovereign faster and go for a quest win... If the fight is 1v1... Was that patched or is it still your army vs the dragonlord?

I like the current system for a similar reason to what Sanati said. Plenty of hero souls at the ready. Due to the current system I tend to do Water/Life in my 'standard' custom faction/sovereign. Then eat whatever I feel like using. Adds a little bit more randomness.

An optional tribute type thing from fame levels sounds alright to me.

I agree. Take a page out of MoM, if you have an empty hero slot (i.e. you have reached a fame threshold). heroes will appear at random periodically until you've filled the slot. 

You could even take this further, and have summon hero spells available (maybe a summoner trait?) or as a faction/sovereign ability. 

It'd also be nice if the game took into account what heroes I do have when the new heroes appeared. It's beyond frustrating because it always seems like I get the same hero classes that I already have in spades (usually it seems to be fighter/defenders).