As mentioned in my OP, I had the SMS lag with 1.1.1. Since then, I downgraded to 1.0.2 (no SMS lag), then later on, back up to 1.1.1. In the process, I chose NOT to restore from a backup, meaning I lost all my system settings. But as others have reported, this seems to have fixed the SMS lag. I no longer have the delay, using 1.1.1.
To do this, first sync your phone so your computer has the latest calendar, addresses, etc. from your phone, then restore the phone, but choose to set up a new phone instead of restore from <your phone's name>. Again, this will wipe out your system settings, dictionary, weather cities, etc...basically anything that can't be synched will be lost, but you *should* see no more lag from SMS.
I suspect there's probably an SMS plist or cache file on the phone from 1.0.2 that causes the lag in 1.1.1. If you're adventurous, you could try to SSH into the phone instead of doing a restore and poke around the SMS related files to see if deleting any of them helps. If you aren't adventurous or haven't jailbroken, restore and start fresh and you should be good to go with no SMS lag.