Ninja!!! Gotta love the ninja. Not only that, but it does complement the thief job pretty well....or so it seems anyway. The only problem is it's an advanced job.

I also like the ranger job as a sub. It looks like a pretty good combo to have with theif, though this one is an advanced job as well...

If you're looking for another starting class as a sub job, I can't really help there, but then I have to ask if you really need a sub job. Is there anything wrong with sticking to just one job, at least until level 30? (This question is for people in general, not just for xlennyx)