I usually find that quoting anything like a realistic price to an internet inquiry makes this dilemma go away very quickly, but it is worth pursuing to find out.
Well printed, a 16x20 can look quite good from 35mm, but as Suzanne mentioned, making them is a challenge. Enlarger alignment becomes very critical (especially negative stage to lens); film flatness; lens quality. I've had good results with the 50mm 2.8 El-Nikkor N (the illuminated f/stop model - the older ones weren't as good), but you also have to be careful not to stop down too far since diffraction loss takes a toll sooner at this magnification (to the lens, it is like shooting a closeup of the negative). A glass carrier is a big help (to me a necessity at that magnification).
If you print yourself and have any interest in making big enlargements, it's a great chance to give it a go on someone else's dime. If farming it out, I'd want to know that the printer is good, but I suppose the few who are left probably are. A non-darkroom solution isn't open to discuss here, but might also be worth pursuing.
Of course most picture buyers really aren't all that fussy about the minutiae that we photographers obsess about.