If the aspect ratio isn't the problem (ie you get 4x6 and the AR of the files is 2:3 already) then ask them if they have a "no crop" option on the printer for digital files. The next thing you could try is to put a 1/8" or 1/4" border around your image and see what happens when it gets printed. My experience with the fuji frontier has been frustrating at times because it crops a little at the edges and really the best solution for me has been to have nothing important 1/4" in from any edge as opposed to going the "no crop" or adding a border route because then I'll have an edge or 4 edges to trim off and really I'd rather not do that. If you get a crooked border on your prints when trying this stuff, don't be shocked. It happens. The frontier than I know (can't think of the model # off hand) cuts the paper before it paints the image onto it. So you'll have a 4x6, 5x7 or whatever size piece of paper being pulled along the paper path to the laser and it almost never stays perfectly square. This is just my experience - yours may differ.
Prints from big box chains... some of them use frontiers.
Many digital cameras make files with a 3:4 aspect ratio or 1:1.333. so if you wanted a 4 inch print from a file with a 3:4 AR what you would want is a print that is 4x5 1/3" roughly. On the frontier, print the 3:4 file on 4x6 using "no crop" = 4x51/3" image with white borders on either edge of the 4x6 piece of paper. 35mm film frames are 24x36mm so they have a 2:3 AR and 4x6 is really suited for that format.
If you can't talk to the printer or they're a complete moron (it happens

) then in photoshop make an action that would pad your 3:4 AR images so that they have a 2:3 ratio without cropping.
1, image size, height = 4 inches (no resampling preferably)
2, canvas size, height = 4 inches width = 6 inches.
With that action you've effectively simulated the frontier's "no crop" option.