i) Depends on how sophisticated you want to get and how much you want to spend. At the cheap and easy end, radio triggers like the Cactus V5s would get you started with good range and reliability. But its not significantly more expensive to get a more sophisticated system. The key question is whether you need a system that incorporates high speed synch.
ii) Canon flashes are well made and you won't have many future compatability problems. But there are a lot of manufacturers out there. Metz has a good reputation for quality. Nissin, Yongnuo, Sigma etc provide similar specs to Canon in cheaper units (of course with build quality to match the price). My own collection of flashes include Minolta, Sunpak, Vivitar and Nissin as I use an antiquated radio triggering system and system compatability isn't a concern for me. But I think the 600EX and Canon's new radio triggering system is a game changer. If I was flash shopping now and it was in my budget, I'd give the 600EX serious thought.
iii) If you are serious about using the flash on the Fuji, you should be looking for one with an auto mode (AKA Auto Thyristor) and/or a manual mode. Unfortunately, this rules out some of the cheaper Canon flashes.
The 600EX has an auto exposure mode. Rather than the camera determining the correct exposure and flash output, the falsh calculates this - you key in the aperture and ISO and the flash uses a small sensor on the front to determine flash output. I haven't used a 600EX (so do a little more reading), but in theory, this should mean that it can work well with other cameras, like your Fuji. You would simply put the flash in auto mode and it should deliver the right amount of flash. If it's not perfect, you would simply dial in some flash compensation. But the beauty is that it will put you in the right ballpark for flash output straight away. The results might not be as consistently good compared with ETTL with the Canon bodies, but it should work well most of the time.
Alternatively, you could also use the flash on the Fuji in manual mode and use a little trial and error. With a bit of practice, you can pick this up pretty quickly.
iv) A multi flash set up gives you some interesting options. Your list of gear suggests you know what you're doing. Given what you normally photograph, do you see yourself ever using more than one flash?
v) Flash stand, umbrellas, reflectors.