Wiping cache and dalvik are the minimum, but if there are any significant differences to the base OS or system apps a factory reset is a very good idea. It also depends on what ROM you are coming from - if you are installing a near stock rom based on the same OS version you are already on then you'll probably be ok with just a cache/dalvik wipe, but if you install the same rom when coming from something more different you likely will not be. So if it won't boot, you've checked the download is good, you don't need to separately flash the kernel, and you've followed all installation instructions correctly, you are using a recovery which is known to work for that ROM and you have the right device version (some carrier versions can need different ROMs), if all of that is OK but it still won't boot and don't want to just give up and try another ROM, then it's worth taking backups (nandroid and app/data backups), doing a factory reset from recovery (cache, data and dalvik) and then installing. If it doesn't work after that then something is wrong, in which case restore your nandroid and try to identify the difference between what you've done and others. But if you've not tried a clean flash (i.e. after a reset) it really is possible that that is your problem: some system data that is not compatible between ROMs prevents the phone booting.
As for theming, some ROMs have their own theming support built in (e.g. Cyanogenmod's theme chooser), others you have to do by hand, e.g. editing Framework-res.apk and SystemUI.apk (which means the mods only work with that ROM), so I would choose the ROM first (I'm not a theming expert, though I've done a bit for my own use in the past). Obviously stuff like icon packs and launcher themes you can do without root, so I assume you are interested in theming the system UI, notification bar, system apps or similar.
