Android phone lost, what data can I get onto new phone?

My Android HTC Magic was lost/stolen last night. I had an unlock swipe code, power-on SIM code and have called the phone company and had it blocked, so not too concerned about the phone itself being used by someone else. What I am thinking about is when I get a new phone, what data/info can I get back easily as I can't just copy it from the old phone now? Obviously GMail/Contacts/Calendar are all stored on the web, any purchased apps are linked to my Market login, and I'm not concerned about photos, music etc that were on the SD card. What I'm more concerned about are my preferences, settings, SMS texts, list of installed apps, prefs, data from those apps, etc. Are those all gone? Addendum: I was thinking of rooting the phone, so did take a standard Nandroid backup a week ago that I have a copy of on my PC, if I get an identical model of phone and restore that, will my data come back? Also what happens if I try to restore that onto a different model of phone (I'm assuming bad things would happen)?