You might try a few labs. First, do your normal adjustments using CS4 and save the file. Then take the file to a few labs and get a print, I would think 4x6 might be a little small for comparisons, so maybe 8x10. Then compare each print with your monitor and see if any of them come close to what you would want your print to look like.
If your lucky, one of the labs prints will be a close match to your monitor and you can just use them. If not that is when color management comes into play.
I do not think you should mess with prophoto, your camera probably has aRBG and sRGB, so you could use aRGB.
Starting with color management, talk with a lab or two that you liked their service or their prints and ask if they have profiles for their printers. If they do then get a copy so you can soft proof your images with CS4. Now, once you adjust your images 'print to file' using let photoshop manage colors and use the labs printer profile. Note-I use Qimage but I would expect CS4 to print to file.
Now take that file to the lab and make sure they turn off color management because you have their profile embedded into the image. Then see how the prints look.
Because you are calibrating your monitor you have to hope your monitors colors are correct.
There is no reason not to use Costco, you can check with drycreekphoto.com to see if they have a profile for any of the Costco's local to you. A quick look at their site shows they have profiles for a place called Pheonix Professional Labs, you could talk with them on how to use the custom profile.
Once you get involved with color management you hope it works, if it does not work then trying to find the problem becomes very difficult. Could be monitor, viewing light, printer, any associated profile etc.
I have a color managed workflow but still is not perfect, my monitor (Samsung SyncMaster 213T) is calibrated with an i1display2, my printer is profiled using profiles produced with MonacoProfiler. Its hard to match brightness and I seem to have an issue with reds/orange that I am still trying to sort out.
Just remember, if your prints come out close enough you might want to keep it that way. Once you start with color management it could just work or open many more issues that become harder to figure out.
But like many here, I enjoy using color management, it just gets frustrating when you can not figure something out.