I'm pretty sure that OS3.9 boots into more colours than that after a standard installation - at least enough to display all the included GlowIcons properly, and usually to make a reasonable attempt at the standard OS3.9 "Get Boinged" background. My guess is 32 colours, but it's so long ago that I don't really remember. One thing to be careful of is to make sure your UAE setup has AGA emulation selected. By default, UAE emulates an A500, which might make OS3.9 boot in a 4-colour mode, since it believes it's actually running on the OCS chipset.
As Aegis said though, RTG is definitely the way to go and is simple to set up in UAE, but even without it, OS3.9 should still be a little more colourful than you're experiencing.