I was actually going to say you might like the Storm2, as it is such a vast improvement headache wise over the Storm, but Krypto might be right. (as usual

)
As far as battery life you're not looking at anything better than the Storm with the Storm2, but I've heard nothing but good things about the 9700. That was going to be my initial suggestion.
If it was up to me (in Fantasy Land) I'd give every Storm owner a Storm2 just so they could see what 'should have been'. It really is a night and day difference, but you might not want to take the chance, which is understandable.
So yeah, I guess I'd go with recommending the 9700 as well. If you don't want to leave Verizon, My only suggestion is the Storm2 or hold out however long for the Essex. They have the 8530 as well, but from the people I've seen with them the battery life is atrocious, on par with the Pre.
And Ayrow, I wouldn't go as far as to say the Nexus One is what the Storm should have been, at all. I don't think anyone was expecting the Nexus One when they heard about the Storm, and if they did it would only take one quick glance at the rest of RIMs line up to realize that would never happen. I think the Storm2 is exactly what the Storm should have been originally, just as the Essex will most likely be what the Tour should have been all along.