I have played 8 times in 2 player game. It does play well. It is tight and we have had military dictate a couple of them but never a military victory. You can use military to keep your opponent down. Most wins have been the 3 leader track. We had the pyramids once and 5 heroes once.
We are only showing 5 heroes to start with and then add 2 heroes every time a hero is taken.
That being said we have agreed to exclude Hercules in our games moving forward (2-player). He is too powerful in 2 player game. As was mentioned the 2 victory point swing is VERY hard to overcome if the game was at all close prior to person getting it.
It has been exposed 3 times and the 2 times it was taken was victory (I purposely avoided it in the 2nd game since it would have been over if had taken it). My dad NEVER beats me in these types of games because he normally focuses too much on straight combat is more tactical than strategic. The only game he won was the one time he took Hercules. He played to get Hercules so I credit him for that but he also knew I was NOT going to take it as it would have been too easy.
Before anyone asks; YES we know the rule in 2-player game you must hold onto victory track lead the entire next round.
If the game is at all close, simply attack and occupy 2 caravans or 2 cities - that will cost the opponent 2 points on the Trade or Political track and boost you 2 points on the same track. That is enough to overcome a 3 point deficit on that track if you are not the current leader (and a 4 point deficit if you are the leader).
If the game is not close enough for that to work, you have already lost.
If you don't have enough military to do that, you have already lost (you don't need all that much, as there are always provinces that are weakly defended, and often several can be reached with only 2 triremes, and 3 legions should be enough to perform this tactic)
Ramses can really help with this situation. The Queen of Sheba can be used to instantly convert a province to accomplish the same as occupying.
There are also other Heroes that can offset most of the advantage of Hercules (e.g. Perseus provides +1/+2/+1 compared to Hercules +2/+2/+2).
So, Hercules provides a decent boost, but not much more than heroes that also have decent abilities.