I know it's silly but I actually have some pretty fond childhood memories of Bonzi Buddy. Me and my cousin installed it on the family computer (running Windows ME at the time!) and would use the text-to-speech feature to make it say crazy, usually profanity-laden, things. In retrospect it was obvious adware / malware but not as bad as some of the other junk that would end up on your PC back in those days. The litany of Internet Explorer toolbars that would hijack your start page and embed HTML on any page you viewed comes to mind.

Some other nostalgic software experiences from this era: chatting with friends and customizing your away message / profile on AIM and ICQ, downloading unreleased System of a Down songs from KaZaA, playing Ultima Online until the sun came up, Flash games and animations on Newgrounds and the overall vibe of the Internet at the time - message boards, 1337speak, animated GIFs and embedded MIDI everywhere. I miss it and don't at the same time.