I have a photograph I want to print and frame in my house, but when I first tried printing it, it came out a bit blurry. How do I fix that?

The original is 3011x2260 pixels and 72 pixels/inch. I initially took that to be printed on photo paper at Walgreens. I printed it out at 24' x 36'. It was a bit too fuzzy.

I have photoshop and my girlfriend found some other program she heard was good for resizing photographs, but we aren't confident what should be done. I can resize the picture, and change the pixels/inch in photoshop, but I don't know if it is doing any good.

What should I do?