I have now won 3 games (one on easy, two on normal. One of the normal games had all 8 races alive with no planet changing hands) and I always formed the federation very fast. I'd say maybe around 3003 in my latest game. I don't know the exact dates anymore, but with the first two spacefaring races I got them to set up as many trade routes as possible. They even could form trade routes with non-spacefaring races. I then just sort of added to the federation as soon as I had the credits to do so; some races were very cheap (Peltians...) others moderately expensive (yes, I tried getting other races to get them to join, I did not just ask them directly).
For credits, the AFA missions are great. In between, when there was nothing to do, I just researched with someone - focussing on the research boosting techs first (there is one which speeds research up by 300% - a few prerequisites, but nothing too bad).