What size boat?
For some reason this question has come up a lot lately. My best advice is that you are really looking for two different boats here; one to learn to sail on and one to go voyaging. Of course, to some extent that depends on whether you really want to sail well or just learn enough to get out of the slip and get back which is actually acceptable to many sailors.
If you really want to learn to sail, I would suggest that you buy a comparatively light and responsive, 23 to 28 foot sloop with a fin keel and spade rudder with a tiller and just plain sail the living daylights out of her until you can make sail adjustments and steer by second nature without having to think about it. I also suggest that you read a lot not just cruising books but books about sail trim and boat design so that you really understand the dynamics of sailing.
Once you have done that for a few years you will know what is the right boat for YOU to take voyaging.
With regards to the smallest boat to "safely sail these distances", when it comes time to go voyaging, my best recommendation is that you size the boat by displacement (weight) and not by length. In a general sense, displacement really tells much more about the size of the boat than length. The traditional rule of thumb is that you need 2 1/2 to 5 long tons of displacement per person to carry all of the supplies, and gear required for distance cruising. (With better gear and the perceived needs for more stuff pushing the upper limit towards 6 or 7 long tons of displacement per person.) So, if you are going to cruising single-hand, you can figure that the smallest boat that you would want to use for distance voyaging in would be roughly 5500 lbs. with perhaps 7-8,000 being a little easier and more comfortable.
Lengthwise, this would be a roughly 27 to 32 footer. Within reason, the longer boat (especially if the length is measured at the waterline) would tend to be more seaworthy, easier to handle, faster, offer a more comfortable motion and have more room down below. While you might be able to crowd this kind of displacement onto a shorter boat, it would come at the price of poorer sailing abilities.
The kind of boat that you might take on a distance voyage such as you are proposing would make a lousey first boat to learn to sail on even if it was virtually the same length as the boat that you chose to go voyaging on. The good news is that the kinds of boats that work well to learn to sail on, can be bought cheaply and can often be sold for what you paid for them a year or two later.