I haven't done much of anything below deity, aside from a co-op MP game at emperor that the other two players quit. My play time so far has been pretty limited though, due to technical issues, so pushing up to speed on deity has been the priority.
I agree that researching and investing a district towards religion early is pretty nasty, but I'm not sure it's enough to offset potentially not having to snag those last few capitals. Even on deity, the AI isn't founding a lot of cities right now (in my current game I have over double the next highest civ, and triple on a few), so it's not like taking a capital is some kind of laser-surgery cut through a 12-15 city empire. If you take 2 cities, including a capital, there's a good chance you've more than cut that nation's production and tech in half...you might have literally taken half their cities on the default map size...
Given that, there should at least be some AI that don't resist your religion too well. For the religion victory to be harder, you'd have to struggle 1) have lost so much in getting religion that you struggle to beat AI nations or 2) somehow struggle despite the means to beat down the AIs who are actually converting anything. Maybe you guys are right, and founding the religion is costly enough to meet these standards relative to skipping it or playing a nation like Arabia or Russia.