I guess it depends on the quality of your original, what resolution camera it was taken with etc.
The DSLR images (8mp and above) will print to A4 or larger with acceptable resolution, unless the bad bits around the edges are cropped out
I've printed some photos of the family in larger than A4 size (taken with a 8mp 350D) by taking my image to Kodak or Camera House.. not especially cheap, but good quality. I've printed A4 size on my home inkjet printer (Epson Stylus CX3100), and it's quite good quality for the price.
I ensure I buy good quality paper and use the highest quality settings.