I think the answer is "it depends"
It depends where and how you are going to look at the picture, how closely you are going to look and if you are the sort of person who will notice technical issues and obsess over them. You might not know what digital noise, grain or smearing look like and you might not care. From looking at the MP count I'd guess that if the pictures were taken in reasonable light and look to be sharp enough you should be able to fill an A4 or even A3 sheet and view it normally. By "normally" I mean at a distance which will allow you to comfortably see the whole picture.
In your place I think I'd look at the prices for whatever size print I was interested in and probably go for it. Any technical issues may not be too great and even if they're there you might not see them if you're not an obsessive geek like many people here on this site, like me

I've recently printed and framed some pictures (not phone pictures) printed to fill an A4. The frames are A4/A3 just bought from a supermarket. I'm very happy with that size of picture and fame on the wall but even A3 would be ok. I don't know if I'd want larger, but why not?
If you do get them printed please call in again and tell us how happy you are.
PS.
You don't necessarily need a printer in London, lots are online these days.