Is there a "clean" Android I can reinstall on my Galaxy S4?
You should try out http://www.cyanogenmod.org/, they have a version of their ROM for pretty much every major device out there. They try to stick to the AOSP (Stock/Vanilla) Android as much as possible. 
If you use a stable version or a mile-release you'll probably never have any problem with it. If you want the latest features, you can use the nightlies, but they might have some bugs from time to time.

On my Galaxy S3 I've got a Android 4.4.2 ROM that is based on cyanogenmod source with some added components. While the stock Galaxy S3 OS is not even on Android 4.3 yet.