With you being a Linux user, I find it hard to believe you couldn't do some of the tings you stated. Usually Linux users are knowledgeable people who know their shit, and since you claim to be one, jesus, did you really use the product at all or make this up?
To remove the dog, CLICK ON HIM, and he will greet you with some options, click the one that says "Turn OFF animated character". Not hard to do.
Removing some MS middleware: you didn't mention it, but you will soon. To uninstall Windows Messenger (the worst of all MS's middleware) go start > run > type in RunDll32 advpack.dll,LaunchINFSection %windir%\INF\msmsgs.inf,BLC.Remove and hit Ok.
So far, you can't remove Windows Media Player and it's a bitch to remove IE, however, they both combined are about 4 MB big, they don't take up much space.
By default, XP has NO desktop shortcuts whatsoever except for the Recycle Bin. But since I think you have an OEM copy from your PC manufacture, they have added all kinda crap. Just right click your desktop > properties > go to the Desktop tab > click the "customize button"
brb