You could try Handcent SMS or Go SMS Pro, both free on the market instead of the built in one. I use Handcent myself. It lets you customise how it looks and has other features (such as repeat notifications if you miss a text). As far as I know you can't change the icons for apps in Touchwiz, but if you download a new launcher from the market (you don't need to root to do this, but some more advanced features might require root to work) you can customise more of teh phone than in Touchwiz. If you want your phone to look more like stock ICS than Touchwiz, you could try Apex launcher (again free on the market) which lets you customise the icons used for apps on the homescreens and the dock. If you download an icon pack for ICS (cant remember where I did, but a quick google search should find one) you could replace all the icons for phone, contacts and handcent with the ones you would get in ICS.
Hope this helps