I'm know this can't be done without editing the applications in some way, so my question is, more or less, is it possible for me to edit certain applications to replace their icons, and if so, how would I do that?

I adore the style of the icons on the Storm, but some 3rd party apps' icons look out of place among all the pretty native ones. I have the graphics capability to recreate the icons to fit the Storm's theme, but I'm not going to get my hopes up.

I'm searching google now, but I figured I'd ask here as well.

Check out How to change 3rd party app icons - PinStack.com, it only allows you to change the icons on your home screen, but it does change them. I haven't tried it though. It also says that he (the author) has trouble scrolling after doing it, but since your on the Storm, I don't see that as being a problem