Depends on what you think of as "grainy". First, know that printed image quality is measured in DPI (dots per inch). DPI is for all intents and purposes the sames as PPI (Pixels per inch, which is how your images are measure. ie When you camera manual refers to an image which is 2500x2000 (or whatever is the case) it's referring to PPI).
Optimal photo-printing is done at 300DPI, so, using the example image size above, that would produce an image of 8.3 x 6.6". With modern high-resolution printers, you can achieve near-photo-quality images at resolutions as low as 220DPI, so that would give you an image of 11.3 x 9".
Assuming that you will be viewing the image at a reasonable distance, you can probably go as low as 125-150DPI, which would yield an image in the area of 20 x 16. Bear in mind that all those sizes are based on the example original image size I picked out of the air.
What I would suggest is to take an image which you think might be suitable for such enlargement and then resample it to the resolutions suggested and print off a 5x7 or similar size chunk and view it from whatever distance you have in mind to determine if it meets your quality standards.