Spies are quite valuable, under the right circumstances. I use tech stealing from spies in the vast majority of my games. Now, the fact that spying is only effective/cheaper than buying on the upper levels is a problem, I would agree....
Propaganda, while much more expensive than war, can be an effective tool. It has its limitations (very strong ones, granted), but I wouldn't call it completely useless. I certainly prefer it slightly underpowered to way overpowered, a la Civ2.
I would argue that Civ3's spying system is a huge leap forward from Civ2.
OTOH, I also agree 100% that it could use improvements. In the 1/3 new, 1/3 old, 1/3 improved model, I'd put this in the 1/3 improved area. Don't throw it all out and do something new but a few small changes to make it better.
My $.02,
Arathorn