If you want to know what sort of boundaries the Shi'ites envision for a Southern autonomous region that a Supreme Counsel for Islamic Revolution in Iraq figure demanded today, look at this map from the last election. The nine light brown provinces in the Southeast corner are it and Juan Cole states that they are starting to call the region by the ancient name of "Sumer". This leaves nine provinces outside the region.
A map at this link shows the Kurds aspirations, although they'd be happy with the part of that map that is within Iraq for now. It claims parts of six Northern provinces (the boundaries were redrawn in an effort to make partition more difficult under the Baath Party regime). Basically, it claims most, if not all, of the provinces of Dahuk, Arbil, Sulaymaniya, and the highly controversial Kirkuk. It also claims some of Ninevah and some of Diyala.
Central Iraq (Baghdad and Salahuddin and some of Diyala), and the Western desert of Anbar Province and much of Ninevah province, would remain less autonomous provinces.
Federalism in some form or another makes an immense amount of sense for Iraq. It allows the Southern Shi'ites and the Northern Kurds to get more or less everything they want politically. And, while the Sunnis are naturally concerned about losing access to oil money, if that is not retained by the central government, they have far greater prospects of gaining a meaningful say in a post-Saddam government in a strong provincial legislature than they do in a central parliament where they are grossly outnumbered.
Oil revenues are the main impediment to federalism. The oil wells themselves are in the South and the North, with the richer ones apparently located in the South. The Kurds could probably leave with their oil wells and break even on the deal (which they would very much like to do if they could avoid military intervention in the process). The Southern Shi'ites, as their leading political party's name implies, would like to follow in the footsteps of Iran and perhaps even join it. But, if both the Kurds and the Southern Shi'ites left, rump Iraq would be left high and dry without the oil revenues that drive Iraq's economy. Anbar and non-Kurdistan Ninevah where old guard Baathist forces remain strongest are also conveniently near Syria which happens to still have a Baathist government.
One can imagine a not so far fetched scenario where a few years after a new constitution is adopted, Kurdistan becomes an independent state (which makes Syria, Turkey and Iran which are also home to Kurdish regions very unhappy), Anbar and much of Ninevah joins Syria, a newly autonomous "Sumer" becomes a province of Iran, and the provinces of Baghdad and Salahuddin and some of Diyala remain as a small, multi-ethnic rump Iraq with none of its predecessor's oil wealth but much of its modern infrastructure and professional class -- a sort of Eastern counterpart to the Kingdom of Jordan. This clearly isn't what the Bush administration had in mind when they set out to reshape the Middle East, but it would certainly change the map and the international dynamics of the region.
The sensible solution for now is to keep the purse strings with the central government, while giving two large autonomous regions and a number of highly independent provinces broad say over how their internal affairs are managed and how their share of the funds they receive from the central government are spent.
Terrorism is a symptom of other problems. The problem in Iraq is that the new government has not yet earned legtimacy with much of the population. The solution is develop a governmental system in which every substantial player feels like they have a stake in the system. I don't see any way other than federalism to achieve that end.