You already ranted about this in your own thread, killaman. And I responded that nukes don't need to be more powerful, they need to be more useful. And ICBMs are the least useful. They're basically last-resort doomsday weapons, and don't serve any purpose in a practical war. You'll just waste time stockpiling nukes to annihilate your enemy (and yourself) instead of producing military units to conquer your enemy with minimal collateral damage.
My suggestion is adding two early generation nukes: the WWII Atomic Bomb and the Civ3 Tactical Nuke. The A-bomb would be bomber-dropped and therefore could be shot down by enemy fighters or AA defences, but not by the SDI. The Tactical Nuke couldn't be intercepted at all, so it'd be the ultimate nuclear deterent because it'd be nearly impossible to find and neutralize them all before they were launched, especially those loaded aboard Nuclear Subs (but then we'd need Nuclear Submarines in Civ4 too). Also, both the A-bomb and Tact-nuke would only damage one square, instead of 9 like the ICBM, because neither are as powerful as an ICBM. The Tactical Nuke especially because it's purpose is to be used in battle at a range of only a few miles, so it's yield and blast radius would be relatively small.