Perhaps you could give a few more details, particularly in regards as to what resolution you're scanning these, and any other pertinent info.
It's possible to get good scans from very small pics, provided the original pic is of fairly decent quality.
I've attached a scan I did not too long ago as an example. The actual dimesion of the photo itelf is less than 1/2 inch tall. It's actually a button/pin my gg grandmother had. I was scared to try and remove the photo from the button, and to be honest I'm not sure how it was even put together

so I just gave it a shot and scanned the whole thing as it was. I scanned at 300 and 450 at first but it didn't give me much size to work with, so I increased the resolution to scan at 900 and it gave me something workable. being the size it was, the high res scan still came in at well under 500k file size.
So the first thing I'd try would be to increase the resolution at which you're scanning, small images like this won't be huge files, and it may help.
Of course there are also many other variables that could result in the grainy look you're getting, photo condition, paper, age etc. in which case higher settings on scans would only increase the graininess.