Behold, the Sunon KDE0504PFV3! This is a nearly silent MagLev series fan that meets all of the needs of the CPU fan. They can be found on eBay for $7/ea (link below)

http://www.ebay.com/itm/271286426922
Now, these fans do not have the tach wire on them, but they do have the tach sensor. I took the wiring off the original fans and soldered them to the new fans, and they screwed right in with the original screws. Just make sure that you take the washer/spacer out.

After everything, the board is dead silent, and did not overheat even after several hours of it running.

I am also looking for a cheap alternative fan for the Naomi 1, as these are slightly too small to work. I will follow up when I find something for that board.