IloveTLRs, you seem to be complaining mostly about grain and film processing issues. Concerning grain, the samples you posted appear much less grainy than the scans I've made of 110 film from the 1970s. I haven't used a 110 camera since then, so I can't compare to film from the 1980s or 1990s. Note that the Web site you referenced also makes comparison to films of the 1970s rather than the 1980s or 1990s. Your photos look about as grainy as I'd expect, based on my experiences with 35mm film. After all, AFAIK the few remaining 110 films use the same emulsions as the like-branded 35mm or larger format films; it's just cut and packaged differently. Therefore, a 110 photo will be grainier than a 35mm photo on the same type of film.
As a practical matter, you might just have to search for a lab that can do acceptable 110 work. Alternatively, you could try scanning on a non-flatbed scanner to avoid Newton rings or at least rig some sort of negative holder to keep the negative flat and a short distance above the glass of your flatbed scanner.