I use an 8 hp on my Oday 23 (which is heavier than your boat (over 3000 lbs.). It is more than adequate. I'm no expert, but I haven't seen an outboard larger than 4 hp with an internal tank, and 4 hp is definitely too small, especially if you have to deal with currents.
For shaft length, 15" is standard; 20" is what is considered a "long shaft". Some manufacturers also offer 25" models. If you can, go for the extra length. The first time you are in any sort of seaway, you will appreciate it.
Also keep in mind that if you buy a new engine, you no longer have a choice of two vs. four stroke engines; they haven't made new small two stroke engines for a few years now. This is good for the environment and your fuel consumption, but also means that you need to make sure your outboard bracket can handle a four stroke engine. There are two reasons you need a stronger bracket: fours weigh more than their hp equivalent twos; and fours generate more torque. There have been a number of threads here debating whether you really need a bracket rated for a four stroke. A number of posters have questioned the need for a four stroke bracket if they (for example) have a 8 hp four stroke engine to be put on a bracket rated to handle a 20 hp two stroke. The 8 hp four stroke weights a lot less than a 20 hp two stroke, but how much of that is offset by the increase in torque? I have no idea.
The practical implications of replacing a two stroke bracket with a four stroke can be considerable. The new bracket might require drilling thru the transom, adding support on the inside of the transom, replacing or augmenting the "spacer" block (that angled hunk of fiberglass between the bracket and transom), etc. Nothing insurmountable, just enough of a pain to make one look for every reason to keep the existing set up.
