I would compare Frontier to the Tradewinds games, all of which I enjoyed and beat. I'm loving Frontier as well, and would love to see a Frontier 2 come out!
Basically the improvements that Frontier 2 would need could be summed up in one word: MORE!
MORE GUILDS!! I really liked how you could join various guilds in Frontier and run missions for them. Frontier currently has 2 guilds, the Buccaneers (piracy), and the Enforcers (policeman). I personally would like to see more missions from the current guilds, and maybe some new guilds - perhaps the Merchant Guild (get lots of gold to win), or a Thieves Guild.
MORE CITIES!! A bigger map would also be a great bonus. Currently there are 50 cities in Frontier (which is a little ironic since one of the achievements says to "Defeat 100 cities"). It would be nice if we could have up to 100 cities, or even more!
MORE WEAPONS!! Or perhaps weapons customization so that various weapons could hit beyond their base damage. Of course, if you could have unreal super weapons in the game, you also need...
MORE ENEMIES!! Different enemies! And maybe even a couple supervillians with unbelievable amounts of HP.