That's pretty much what I've been doing too, and I agree with your conclusions.
The HP Bonus is very nice to change. I gave ancient units -2, early middle ages -1, gunpowder 0, and then Infantry-up +1, and changed the base HP's to Conscript = 3, Regular = 5, Veteran = 6, and Elite = 8. Unfortunately, I came to realize that one elite unit in the ancient age is pretty much unbeatable, since 2 HP's is next to nothing. This may be realistic, but it's not too fun if you don't have any elite units. So I changed ancient to -1, and set the base HP's to 3, 4, 5, 6. So the first big jump is when gunpowder comes along, so now it's a good thing to shoot for.
Another big change I tried is giving foot units 2 moves, and increased all the mounted units moves by 1. So far, I like it. It erases the advantage of retreating, but speeds up warfare.
Finally, I gave most ranged units a bombard attack, and increased the punch of siege weapons. It works much better. At first I thought it would give attackers an unfair advantage, but the ability of the defenders to run out, attack, and run back in, as well as bombard, counters it perfectly.
As far as the new units needed, earlier gun units are a must. I put in two new levels of infantry, Dark Sheer's musket infantry and then SM's flintlock infantry, and it works great. We really could use an extra tech in that area, so I've been thinking about changing "Free Artistry" to "Tactics" or "Leadership."
Also, I added a Men-At-Arms unit for medieval infantry, and he seems right at home with Feudalism.
And I agree that the ships need to come much earlier.