Are you playing Pangaea or what map type? I used to play Huge/Pangaea or Huge/Continents at Marathon speed. It's true that you can get more cities than on smaller maps before attacking the first civ, but I still found that an Axeman/Immortal/War Chariot rush is effiecient. You're likely to build more units anyway since there are more barbarians and a few of those will get nice upgrades that you can use in your first war. Don't let the distance hold you back. I usually built the cities a little more scattered anyway since the resources were farther away, and I'd soon be close enough to another civ to be able to attack and reinforce my troops if necessary.
Maybe you can post some screenshots and we'll try to decide together if a war is possible/needed or not.
