It depends more on the file size then the format of the file.
What file size do you have? What sensor/camera is the file from?
I am very comfortable with 11 x 14 paper with a 9 x 1/ image size. This gives me a standard uncropped image. It's my standard size. I've made 16 x 20 & a few 20 x 24's and I am very happy.
Most online printers prefer jpeg files. So I shoot raw, make a tiff in LR and convert to jpeg for printing.
Hope this is a start.
If you want to enlarge any image you are using interpolation which means the program 'makes up' the new pixels based on what is nearby. This leads to degradation of the image as you have alluded to.
Suppose you want to increase the size by 50% from say 4000x3000 pixels to 6000x4500 pixels. The number of pixels goes from 12 million to 27 million - that's a lot of new 'made up' pixels.
There is a strong belief that it is better to use no more than a 10% increase and to repeat the resizing in 10% bites till you get to the size you want.
There is software that will resize with minimal quality loss such as onOne's Perfect Resize (previously called something like Genuine Fractals). I have this software and you can probably download a trial.