You got big balls. How do you deal with the unit spam / religion?
I think you'll find that if you can get the early lead/equality by taking cities, and keep your army in the middle rankings, you won't have much trouble with competing civs militarily. And when you do, it's all about the archer line behind some melee and playing defensive. I usually have more archer units than other units combined. When a war begin, I turtle up -- whether I start the war or not. That could be in my city areas or just in a good defensive posture outside it. You just have to let them come to you the first 10-15 turns. You should be able to whittle them down this way. Trying to go on the offensive early is a recipe for getting flanked and fucked since none of your units, especially melee, will be fortified.
Also, defensively, walls are super important, so don't skimp on them. In new cities, I usually build them first unless it doesn't have fresh water (then it's granary to walls).
As for religion, that's a little more annoying. It's also one reason I play on Immortal instead of Deity -- with some hard work I can almost always get a religion in Immortal but rarely in Deity. If you get your religion you should spent your first apostle on starting an inquisition then make an inquisitor and park it in your holy city. That way, no matter what happens, you'll be able to reclaim your holy city at any time. From there, it's about making apostles and making sure to save the ones that have +20 religious combat. They will completely destroy other apostles. If you get overwhelmed and you don't have enough, park them inside cities, wait for the enemy apostles to spread/leave, then bring them out and get your inquisitors working. Also remember that the holy site and adjacent tiles heal apostles by a lot, so keeping them around there is a big help -- the healing is something like 30-40 each turn so if the enemy is near it's a great spot to let the enemy commit suicide. I have found that I can usually get by with just 3-5 apostles in my territory if I manage them right. Early on, before you have enough faith to get that many, you just have to wait them out and pick your battles, always making sure to keep an inquisitor around to reset the holy city.
I rarely get a great religion because of AI bonuses and choosing inquisition first, but that's not really the point. It's about making sure that the AI can't get a religious victory, which is a much bigger deal the smaller and less watery the map. Most games, I only have 1 or 2 holy sites and have very little trouble with AI religion spam, if that gives you any indication of it not being about making apostles but using them the right way.
There's also a city state (Yerevan, maybe) that lets you pick your apostle upgrades. So, you can make all your guys have the +20 bonus and they'll crush apostles for 50-70 damage while losing only 15-25.