I actually think that the current implementation of nukes is better than in any previous civ game, but I still Agree with Thal's core point that they're overpowered. As with any civ game mechanic they have to tow a careful line between being a) somewhat historically accurate and b) good for gameplay. I think you can make a case for them being overpowered judged against either of these criteria. (The following discussion assumes we are talking about ww2 style fission bombs rather than the later hydrogen bombs).
Taking first historical accuracy.
1) Civ 5 atomic bombs always cause 50% casualties on a city. If we compare this to real life then the Atomic bombs dropped on Hiroshima and Nagasaki caused somewhere between 25% and 50% casualties. Admittedly the sample size here is pretty small but given that a) these bombs were dropped on a completely unprepared populus, b) these cities were carefully chose to maximise casualties and c) the bombs had a fixed yield so dropping them on a larger city wouldn't have lead to higher casualties it seems unlikely that a 50% casualty rate for a city would be the norm.
2) Bombs dropped from planes are heavily dependent on control of the air. The US was only able to drop Atomic Bombs on Japan with impunity because it had complete control of the air. In real life, it is therefore reasonable to assume that strong air defences would be a good defense against atomic bomb attack. The lack of interception of Atomic Bombs is therefore completely unrealistic.
3) The concept of fallout in the game is completely over the top as air burst weapons produce relative little fallout. The population of Hisroshima for example took less than ten years to return to pre war levels and today is a bustling city of well over a million.
Now granted this would all be irrelevant if the Civ developers had simply sacrificed a bit of historical accuracy for a more fun game, however I don't believe thy have:
1) As Thal has stated, in many situations Atomic bombs means game over (meaning a victory for the human just as often as the player I might add). This is a situation that I think Civ games should avoid as much as possible. For an comparative example consider that it would be historically justifiable to make the first civ that gets machine gun era technology (infantry?) virtually unstoppable. This isn't done because it would be detrimental to the game.
2) There are no negative consequences to using atomic bombs so there are no reasons not to use them. This is slightly immersion breaking for me as I want to believe I'm controlling a civilization, not playing a spreadsheet. Yes, you should be able to use atomic bombs, but firstly it should make all other powers extremely cautious of you (and those without nukes actively distrustful/hostile) , secondly it should make your own people seriously unhappy and thirdly it should make the people you used it on even more unhappy!
So that's the argument, now what do I think shout be done about it:
1) Reduce A-bombs to kill only a third of the pop. Maybe introduce a maximum number of pop to kill.
2) Allow interceptions of A-bombs
3) Give an unhappiness penalty for using a-bombs. Ideally they'd bring back war weariness here so it could be built into that.
4) Much reduce the effect of fallout.
sorry for the long post