With regards to foreign policy, I think a 9/11-less US would be a lot more focused on Asia.
There was the Second Battle of Yeonpyeong, as well as the incident where Chinese and US aircraft collided.
China's global ambitions likely develop as OTL, while I am lead to believe that a lack of long-term US involvement in a Middle Eastern conflict precludes Russia from intervening in the South Ossetia conflict. In turn, this leaves the Russians less emboldened to take aggressive actions with regard to their other neighbors. If NATO still expands into Eastern Europe, however, the Russians may be pushed into the Chinese camp nonetheless. Russia's energies are directed in much the same way as OTL, though perhaps with less success due to fewer opportunities to exploit US involvement elsewhere or unwillingness to act. Alternatively, if the Russians feel threatened by the expansion of Chinese clout and influence in Central Asia or the Far East, the Russians could turn their attention in that direction-- Russia would look to India and the post-Soviet 'stans for cooperation; perhaps even Iran if the latter gets involved in Afghanistan against the Taliban and the Russians feel worried about terrorism.
One point that has been brought up by posters in previous conversations is that without OIF, Qaddafi is never dissuaded from continuing his WMD program, so that becomes a problem for whoever is (re)elected in 2004 or 2008. The most likely response is the imposition of a no-fly-zone and a sanctions regime similar to that utilized against Saddam. If the West has sanctioned Libyan oil and Qaddafi's rule is looking tenuous because the coffers are drying up and the ideas of the *Arab Spring are floating around, Qaddafi may decide that his WMD program will have to go in order to re-open his country's economy to Western consumers.
As for Iraq, it probably collapses into civil war when Saddam dies, or alternatively collapses into civil war when the *Great Recession hits and people start protesting. Iraq and Syria might end up as one big warzone just like OTL.
Overall, we probably see the inevitable Pivot to Asia happen under the Bush/Dem '04 administrations rather than during Obama's time in office.
Terrorism is a much smaller concern, at least as far as attacks on the homeland are concerned, but the Middle East itself might be just as important. The Great Recession is still probably going to happen, and with that an *Arab Spring which will leave both Iraq and Syria in sectarian conflicts remarkably similar to OTL. One wonders what the US might do if it is not so war-weary.
Heightened competition with China means that economic and military aid to African states increases in order to combat the growth of Chinese influence on that continent.
The US likely deploys troops to conflicts in Africa as well as in Iraq-Syria in a manner similar to the humanitarian interventions of the Clinton administration-- US involvement likely occurs under a UN or NATO aegis and enjoys broad international support. Actual troop commitment on the part of the US is also reduced due to greater international support. We may find ourselves bombing the Assads' or the Husseins' forces similarly to the aerial campaigns we undertook against the Serbians in the 1990s.