I've used a craptastic Xperia X10 on 1.6 and 2.1, Motorola Droid, an original Nexus and a Nexus S. All of them managed to bring up the Messaging application instantly.
If the Android OS was to blame then wouldn't I have had issues with it?
And I'm using an HTC Hero which is supposed to be one of the "bread and butter" Android phones, not super fast but not the slowest either.
The HTC Hero was the first HTC Android phone with their Sense UI so I wouldn't call it a representation of the stock Android OS which you're blaming. What version of Android is on your HTC?