The spell version of Genesis is in Deities & Demigods. It was originally a 9th-level metacreative psionic power in the Psionics Handbook, available to psions. The spell version is more or less the same, a 9th-level cleric spell in Defenders Of The Faith, and a 9th-level Creation domain spell in Deities & Demigods, with one or two minor changes (i.e. I think the spell version couldn't be used for an antigenesis, sadly). Manual Of The Planes included a power similar to Genesis for the Plane Shifter prestige class, gained at 10th-level in the prestige class if I recall. The psionic version is best however, especially since psions can learn the True Creation 8th-level metacreative power, which creates permanent objects of nearly any material, allowing a psion to mentally create their own structures and whatnot in their personal demiplane.
As for suggestions.... I'd suggest you Planeshift or otherwise transport creatures to the demiplane, potent monsters your evil maniac can snatch from around the Prime Material, to populate your demiplane with unwitting defenses against lesser invaders. Most likely, take creatures that can't fly, travel extraplanar, or burrow through metal. Since Genesis allows you to determine the geography and composition of your demiplane to an extent, create your abode within a custom, gigantic valley that is ringed with thick metal deposits all around the edges, to keep critters from burrowing into your estate, and make your buildings with metal or something (heck, you could probably shape the geography to create hollow, metal mounds wherever you wish, and do just a little real work to make them into mighty fortresses!). Just note that with Genesis, you have to designate any geographical features or patterns at the time you cast/manifest/activate the Genesis. So write up a good, detailed description of what ya want, and your evil overlord can stand atop his mountain-fortress of solid mithral and laugh maniacally in his invincibility!
Anyway, btw, according to Genesis and the Plane Shifter's limits with their Demiplane Seed ability, I don't think you can grant your plane particular energy traits, time traits, sentience, or other wierd stuff..... In any case, the Genesis power description says specifically that the environment is determined at manifestation time by the psion, as long as it is approved by the DM, and no environmental effects can exceed the potency of a 3rd-level spell/power. It also says specifically that Genesis cannot create life nor construction (though what I mentioned above was merely hollow mountains and such of mithral, hehe, not actual buildings; you'd still have to somehow shape or carve parts). The demiplane will be linked to the Astral and Ethereal Planes (via a color pool and an ethereal curtain, respectively).
The Genesis spell in Deities & Demigods supercedes the one in Defenders Of The Faith, but differs from the psionic power too......you'll have to check it out yourself. It's less specific on some points.... Naturally, all of this is up to your DM's adjudication and judgement.