Well, here's my opinion:
Yes, 5.0.1 is a tethered jailbreak but I've been running it with no problems. Granted, it's only been a week, but still, I like it. Rebooting, should you need to, is really quite simple. But, I've not needed to reboot since the first day when some of my Cydia tweaks needed a reboot on installation.
I say all that to say that I'd recommend you go to 5.0.1 tethered. iOS 5 is light years ahead of iOS 4 right now and everyone is now developing for 5. So, you might run into the same troubles on 4 as you did on 3 (developers moving past that old iOS). Note that this includes jail break tweaks developers too...
So, there's that. Good luck with your decision.