As I have tried to point out numerous times, just because OS3.9 gives you coloured icons and backdrops in ReAction/ClassAct apps you dont _have_ to use those, there's nothing in OS3.9 that really makes it so much slower than 3.1. Install 3.9 and replace the icons with those of 3.1 and voila, you have your speed back. If picture,datatype that comes with 3.9 is a problem, then just use the one from 3.5, or 3.1 instead, or a third party one.
My minimig is currently running OS-3.9 with MagicWB icons, and use less than 20 secs to boot, but then I have made a custom 3.9 kickstart so it doesnt waste time rebooting (or RAM on updated exec, scsi.device, fastfilesystem, shell, ram-handler etc). I've also been using OS-3.9 on my A600/030 for years and it's certainly not slow.