Strangely enough, Money Marts in downtown had the best rates, with only a small, flat service fee...even for some of the non-standard currencies.

Last year I wanted to have some Yen before I landed in NRT - their rates were only fractionally higher than the official exchange rate, and they charged $2.50 as a flat fee.