The 3.9 icons are designed for a higher resolution screen (640x400 or higher), so you may want to consider replacing those. Zillions of options on Aminet. MUI comes with some nice textures that you can use in WBPattern (I'm fond of MarbleDark myself). Beware of chip RAM limitations, though.
Magic workbench for the win. There are plenty of decent icons suitable for those pesky 1:2 aspect modes too.
