I know it's a little late now but I thought of one other thing you might want to be aware of. You may actually be limited by the resolution of the printing process. Let's say for example that Staples can only print this particular product at a maximum of 175 DPI. Hopefully it's higher than that, but that's what they say on their web site for small/medium/large posters anyway.
If you fit your photo to the 8x10 area so that the width of the photo is 10", then the full-res image would be 713 DPI and the 5MP image would be 259 DPI. Well, if Staples can only print this at a maximum of 175 DPI, then both the 5MP and full-res images would have to be resized down - just like on your computer screen. Then the question of which image would yield a better end result would come down to a battle between resize algorithms, which is a little tricky.
If you provided the 5MP image to Staples, the processing path would look like this:
38MP from sensor [resized by phone to] 5MP JPEG [resized by printing process to] 175 DPI
If you provided the full-res image to Staples, it would be:
38MP from sensor [stored by phone as] 38MP JPEG [resized by printing process to] 175 DPI
Normally that second path should yield print quality that is visibly greater than or equal to the first path. But if the printing process somehow used a poor quality resize algorithm, you could end up with the same problem you saw on your computer screen. That really shouldn't happen, but it is possible. I don't have much experience handing stuff off for printing, but given that people in printing regularly need to resize high-res photos down to sometimes very small sizes, I would expect their process to be able to handle this correctly.
So, depending on the resolution of the printing process and the quality of their resize algorithm, you could get better results by giving them the full-res image, the 5MP image, or it might not even make a visible difference. The best way to know for sure would be to try both and see what happens, but I think the odds are well in your favor giving them the full-res image.
Now I'm really curious how your print turns out.
