Go to the stickies for this subforum and read The Type of Machine You Need To Sew Leather. After that you'll have a much better idea what you should be looking for.
I'll add that shoes are a whole different animal to most leather working.
Oh, and in addition to your primary anticipated use, consider your heaviest anticipated use. A garment machine, for instance, probably isn't going to be any use for a knife sheath.
EDIT: actually, here's a thread asking about that very machine. Might be worth reaching out to that member for their experience.