An inexpensive lab that allows profile embedding is Adoramapix.com. They do a good job, and their color management matches mine quite well, unlike some others. Labs catering to professionals and serious amateurs either allow embedding, such as Calypso Imaging, or do not require it, such as West Coast Imaging. Both of the latter two labs are much more expensive than Adoramapix. The main drawback to Adoramapix is that they only take files less than 40 MB.
I find prints from Calypso Imaging come back too dark, unless I brighten them up in levels about 1.30. However, this doesn't seem to be necessary with prints from WCI.
More about dark prints in a separate post.