Not much wrong at all with Windows 95. I also have a system running WFW3.11, and its connected to the internet, does emailing and ICQ.
I would recommend using IE4.5 or IE5. But you should be able to use IE4 without too much trouble. It all depends on how much RAM the box has, and what CPU you have if you want to go higher. I dont think you should jump right on updating IE. Try the stock browser for a few days, see how everything goes. You might want to also consider an alternative browser to IE, which should lower the RAM consumption. You can find many older versions of just about any web browser at
http://browsers.evolt.org/