The lab photo printers are likely to be dye-sublimation, or silver-halide (where the digital image is projected onto normal photo paper) which unlike lithography don't require halftoning, however they still use ink and thus follow the subtractive colour model, so the principal is the same.

The reason your colours were off is probably due to CMYK conversion using a different colour model than the one the printer uses (Photoshop defualts to SWOP CMYK, which I believe was developed for an offset print process), as the dyes in a photo lab printer will be different in colour to the ones used in lithographic printer and so require different quantities of each colour in order to [try to] replicate a given RGB value.

Unless advised otherwise by the printers you're probably best using the widest gamut available to you (usually Adobe RGB, which will likely contain 99% if not all of the printer gamut) and let the printer handle the CMYK conversion. You can ask the printer for a colour profile for their equipment in order to have more control over this process and "soft proof" the expected results on your monitor. But unless you need to edit the image in CYMK (for example to get a specific black mix) doing the coversion yourself will just create much larger files (since you can't use jpeg for this) and runs the risk of incorrect results if done with the wrong profile.

At the end of the day producing artwork for a subtractive print process using an additive output device (i.e. a computer monitor) is error prone. It will take several attempts to get the colours how you want them when printing.