Reduce the image size in stages and sharpen each time
Works well. Start out in a 196 resolution. If you go to high, the sharpening will look awful.
best with those type of images to use vector and not raster the imaqe as such
This is very true. I use Vector Magic. I indulged and got the desktop version (Way overpriced for a one trick pony, but it's the best at what it does any where)
My Avatar is from a 1600x1000 wall and VectorMagic allowed me to keep the detail when I shrunk it down. It's excellent. It allows you to save in bmp and png.
For most of my icons, I work with a 500x500 canvas. For the st of toolbar icons I did for the trollthumping suite, I started with a 256x256 canvas becasue I had the same problems you're having. (pre-VectorMagic)
In Photoshop, I found setting your shapes to 'snap to pixel' helped a great deal with 'fuzzy edges'. Also 'Slect>Modify>Contract' about 1 pixel witll help as well with cleaning up the edges.