If a place is telling you that they only print at 100 DPI, that should be taken as a strong warning sign that the place is not running a professional quality service.
Most quality places should be able to print onto light-sensitive silver-halide papers (such as Fuji Crystal Archive) with a Fuji Frontier, a Noritsu, a Chromira, a LightJet, or similar, at at-least 300 DPI (though it is questionable whether higher than that has much benefit).
What size print are you looking to make? If it is 12"x18" or smaller, then you're best bet is probably Costco. They use Dry Creek printer profiles, so you can get your system profiled and calibrated so as to know how the output from their machines will look with good accuracy. They'll give you a continuous tone, 300 DPI print on Fuji Crystal Archive paper for for $2.99. They get it done in a few minutes, and, if there is a problem, they take it back and reprint it, free and with no questions asked, within a few more minutes.
If you want to print a really large picture, the best price for professional quality that I know of is El-Co:
http://www.elcocolor.com/
If you don't want to go with El-Co, then another great option is White house Custom Color:
http://www.whcc.com/
If you want the absolute best quality, price-be-damned, then you want either Laser Light Photographics (
http://www.laslight.com/ ) or Calypso (
http://www.calypsoinc.com/ ) or West Coast Imaging (
http://www.westcoastimaging.com/ )
Mike