Hand size doesn't have that much to do with handle preferences, assuming you have a decent grip. More about handles and grip in a bit.
If you want to do a good job without dealing with the learning curve that is freehand sharpening, there are three excellent tool and jig systems which make the process a lot simpler. These are the two Edge Pro systems and the Wicked Edge. We can go into more detail if you like.
There may be more than one good, home-use electric knife sharpening systems, but the only ones I know of are the various Chef's Choice electrics. These will give you an adequate edge without doing any harm to your knives -- as long as you follow the instructions and use the machines correctly. They are incredibly easy and convenient to use.
You might also consider the Minosharp 3 stage as an alternative to Chef's Choice.
Sharpening services usually aren't a good choice -- if for no other reason than you're without your best knives during the turn around period. In addition, most ordinary services take a "one size fits all" mentality which won't serve exotic knives; and frequently use machines which don't suit the particular knife. Many services, Sur La Tables for instance, use the same Chef's Choice machines you can buy yourself.
Getting back to handles...
Unfortunately, most of the impressions you gain with a brief in-store try out don't hold when you get the knife home and start using it for longer periods, day after day.
There are some injury and ergonomic issues which do make a difference in terms of which handles will and won't work, but ordinary hand size isn't one of them. There's no reason you shouldn't be able to use any of the wide range of ordinary handles. If anything, your smaller hands give you more versatility.
One of the biggest issues in grip is sharpness. They seem disparate, but there you go. Why? Because a dull knife requires more effort and a stronger (i.e., tighter) grip. On the other hand a soft grip is more comfortable and provides significantly more agility.
The MAC Superior is a great bread knife, and my first recommendation if price isn't in the equation. If price is important, the Forschner 10.25" wavy edged bread is very nearly as good. I've never used the Tojiro but have heard nothing but good things.
Paring knives get abused and used up usually quickly. Consequently, the best choice for many people is something which can be both easily sharpened and thrown away after a couple of years without regret. Take those things together and you get Forschner.
For most people moving up to a very good knife, I usually recommend a Japanese knife at or near the top of their price range... but there are exceptions. While I have a few favorites which I recommend most often -- especially the MAC Pro -- there are a lot of great knives out there. If you don't think the MAC will suit, there's no reason you shouldn't find something more appealing.
For a lot of reasons, I'm not a big fan of Shun chef's knives for that same group of most people... but again, there are exceptions.
As to the rest... it really comes down to how much you're willing to spend and how far you're willing to go regarding sharpening -- and in your case, how willing you are to let go of your preconceptions regarding your own grip.
What do you think?
BDL
), so I'm not too worried about the prettiness (or lack thereof, in this case), as it's not worth it to me to go back to Blaine, WA (a 35 minute trip w no border line up) to pay to ship it back to Mark and to have to go back again to get a new one once it arrives. I don't want to be that guy. I'd just like to round out the tail of the handle a bit as those edges are sharper than some of my old knives. 
