In general 'lighter' fuels with less additives will mean that the stove needs less cleaning. Most of the reason I've needed to clean a stove is from additives which don't burn properly (particularly when igniting the stove) can can block the nozzle and things.
For this reason compressed gas (not gasoline) is probably best, followed by Coleman fuel (white gas), petrol (gasoline) and paraffin (kerosine) bring up the rear. I haven't really used paraffin enough to know which is better.
Having said this the biggest risk is that most multifuel stoves (at least the MSR whisperlite) have different nozzles for different fuels. Using the wrong nozzle is the easiest way to block it, particularly using the white gas/petrol nozzle for paraffin.
The other big source of soot is lighting the stove. If the stove needs preheating to burn this involves burning fuel under atmospheric conditions. The fuel burns inefficiently and will produce lots of soot. Once it is burning well little soot should be produced.
I'm not sure if fuel type has a significant effect on o-rings etc. I wouldn't think it is significant. The only advice I've been given on that is to not store your fuel bottles pressurized. There are probably several reasons why this is a bad idea but forcing fuel into the seals for a long period isn't likely to do then good.
Conclusion: If you use it well any fuel shouldn't require much more maintenance, but gas and white gas are probably easiest.