Using the Wiki (and my own, shittier table), here’s the amount of fame you’d get from killing the Nightmare Colony at lvl 1:
First off, you’d get 40,000 EXP to start with.
You’d end up in stage 2, since to get to stage 3, you’d need 45,000; therefore, you get the 20 fame from stage 1 (20,000 EXP); then, you still have 20,000 EXP in stage 2, which is 20,000/500=40 more fame. Total fame earned: 60, excluding bonus playtime fame.
I’d say the most ideal start would be at 71 fame, but I’m not entirely sure of it.