Theorically you should be able to stand an army as big as your neighbours. For that it is required a huge population and military buildings. I won't say it is working right because I still haven't tried a tall game with the new supply limit. Walls and the like give +10% pop to supply limit, so a 20 pop city with castle and armory should add 6 supply each one. Being coastal is a bit troublesome. Lighthouses don't increase supply, but you need a fleet to defend your cities. This means you are left with a rather weak army until Harbors, and even then. One thing you could try is to avoid coasts, something I never do myself.
G said that anyways a tall civ doesn't need so big an army to defend itself, but being continously attacked for being a weakling is no fun (well, it is fun for a while, then it stops being fun). In higher difficulties, AI is supposed to add the player tactical skill (given in part for the difficulty level you wish to play on) into his military strength. Another reason AI should be attacking you is when you are clearly winning, but I've never been attacked for this reason, even when I was clearly winning.