Active Undelete is one of the better ones to try out. But that's also a retail product. One freeware that looks like the one you could use would be Disk Investigator since that is able to examine both NTFS and Fat32 partition types for lost or accidentally deleted files. That can seen and downloaded from http://www.freewr.com/freeware.php?download=disk-investigator&lid=2492
Deleting files depends on what files you are deleting to have any effect on the OS installed. You don't see damage to hardware simply by deleting files from Fat or NTFS while NTFS is the far better file system to be running at this time anyways.
The recovery programs mentioned earlier will easily work on both partition types making the question of which being better for recovery non existant in that sense. Access to files while Windows is running is a dfferent matter due to the increased in security seen in both XP and especially Vista. That's the only thing that could stall recovery if the program is run in another version of Windows and not run independently.