Film Formats
Film format is a decisive factor for image quality. More film per frame means more information available for prints or projection, meaning sharper images, more differentiated colours or grey tones, and so on. When you compare an excellent camera of a given film format to a mediocre camera using a larger film format, then the latter is likely to yield better images.
The most common film format since World War II has been 35mm. It has been invented by Oskar Barnack in the 1920s using cinematographic film with doubled frame size, i.e. 24x36mm. Its frame size is 864mm˛, its frame diagonal is about 43mm. Thus in its early years this format was known as double-frame. Today 35mm is being used both by amateurs and professionals, both by journalists and artists - almost everywhere. When you say you want to buy "a roll of film" then you probably will be given a roll of 35mm film which is 1.65m long thus yielding 36 frames, being in a light-tight aluminum cartridge.
There are at least four common film formats smaller than 35mm: First, Minox 8x11mm film. This type of film is being used by the famous Minox "spy" cameras made in Latvia (Riga) and Germany (info page by eBug). Today the Minox TLX is the standard production model. Its frame size is 88mm˛ (about 1/10th of 35mm), its frame diagonal is about 14mm.
Second, half-frame. This is as large as the original movie film format which was known as single-frame back then (18x24mm). Confusing, isn't it? It uses 35mm film. Its frame size is 432mm˛ (1/2 of 35mm), its frame diagonal is about 30mm.
Third, APS (Advanced Photo System) format. This has been created some years ago by the leading film manufacturers to increase their profits. The problem is that - similarly to Minox format, but that extreme - that not many types of film are available in APS format. The maximum frame is 16x30mm, which is being cut e.g. for the "panoramic" format (which isn't panoramic as soon as you realise that it's only cut). Its frame size is up to 480mm˛ (5/9 of 35mm), its frame diagonal is 34mm.
Fourth, Robot format (German language info page by Rolf Beltermann, Hans Grahner, Claude Bellon & Michael Ensel), sized 24x24mm to save film when it was still expensive. It also uses 35mm film. Its frame size is 576mm˛ (2/3 of 35mm), its frame diagonal is about 34mm.
Summary of 35mm and smaller formats
To summarize, I do not understand why anyone would want to buy an APS camera. You get a smaller film format resulting in less image quality, you cannot buy as many types of film as with 35mm, you may have problems with buying and developing films abroad, film is more expensive, development is more expensive, prints are more expensive, slides are not available, black-and-white is hardly available.
APS' only advantages are smaller cameras, mid-roll rewind, and magnetic data storage. But then again, there are very small 35mm cameras available (like the Olympus mju), wasting some frames on a 35mm film will be cheaper than getting APS for mid-roll rewind, and data imprinting functions are also available by many 35mm cameras.
In short: With APS, you only pay more, and get less. If you really need a smaller camera, you will probably be better off with a half-frame or a Robot camera (although these two formats aren't in production any more, apart from a Belarussian half-frame camera called Agat-18K), if you really want a "spy" camera you will certainly be better off with a Minox camera.
35mm offers reasonable miniaturisation while offering all options that any photographer could want. It is simply the most flexible film format available.
Now let's turn to formats larger than 35mm. First, there are several true panoramic formats using 35mm film, like the 24x58mm used by the Horizon 202 by Zenit, the 24x65mm used by the XPan by Hasselblad, or the 24x66mm used by the Noblex 135 by Kamera Werk Dresden.
Second, there is medium format. According to the Germany Industry Standards DIN, every film format which is larger than 35mm and smaller than 9x12cm is medium format. Actually this standard means that the true panoramic formats mentioned in the last paragraph are also "medium format cameras". Medium format in the narrower sense however today means film formats using roll film. The most common roll film is type 120, a 1.20m long roll of paper-backed film rolled onto a plastic spool. Possible film formats with type 120 roll film are 6x4.5cm, 6x6cm, 6x7cm, 6x8cm, 6x9cm, or even the giant 6x17cm panoramic medium format used by the GX617 Professional by Fuji. While in the earlier days there were also medium format cameras using sheet film, today almost any medium format camera is using roll film, the most common frame sizes being 6x4.5cm, 6x6cm, and 6x7cm.
Third, there is large format. Large format simply means that the film is at least 9x12cm large. In the U.S., the most common large formats are 4x5" (being a bit larger than European 9x12cm) and 8x10" (being a bit larger than European 18x24cm). Large format factually means sheet film, i.e. single sheets of film loaded in total darkness into light-tight film holders. But as far as the film choice is concerned, large format is also the most flexible format, because you cannot only use sheet film and Polaroids, but there are roll film and 35mm backs as well.
So which film format should you choose? This is an important question as it determines the cameras you can choose afterwards.
If you want an all-round camera for family photography as well as travel or sports photography, or anything else, then you should certainly choose 35mm. It is the most common and most flexible format, so you really cannot do anything wrong when choosing it.
If you however want superior image quality and are willing to learn all the concepts of photography, then you will probably soon reach the end of 35mm's possibilities. If you want to do studio or wedding photography, or calendar photography, or serious landscape photography, then you will be better off with a larger film format, possibly medium format.
If you are however willing to give up all comfort of modern photography, and simply aim for the best possible results, then you should choose large format. But only if you are really, really serious. Large format will probably also be your format of choice when you want to do serious architectural or product/table-top photography, due to the many perspective control features offered by most large format cameras (avoiding converging lines, controling the plane of focus, and so on).
If you do however want a "spy" camera for inconspicuous photography anytime and anywhere, and you are happy with post-card sized or smaller prints, then you should probably choose a Minox.