Ukyo is the strongest character in SS2 bar none. Jubei is also way up there (though Charlotte is stronger).
The secret to getting decent at SS2 is to know your normal attacks as well as your special attacks.
Ukyo's low A is a great, fast poke. His low B from a far range is a slower, more combo-friendly slash that works great, but it overlaps with his close low B, which is slow overhand slash that will usually get you killed if you whiff it. His close standing B is another great combo move, but can be ducked under.
Ukyo's main combo is with his qcf+K after-image attack. The C version is fastest but it can sometimes miss crouching opponents at very rare distances, still it's generally your primary combo move. The D and CD versions are harder to avoid but slower. Save these for combos after his close standing AB. There's also a bastardly trick you can do with the after-image slash that involves some timing, but it shows how broken Ukyo is as a character.
Ukyo's other main attack is his swallow slash, jump, db/d/df+slash. Don't even bother doing it after a forward jump in the air. The best thing about the move is that, like in SS1, it can be done "off the ground" with db/d/df/f/uf (or all the way up if you don't want to move forwards). Since it counts as an "air" attack, it's an instant overhead. Actually works sometimes on the CPU as long as you don't abuse it. Against human players, you can use this as a follow-up fake out after a blocked after-image, a blocked low C kick (very fast and hits low), or after a jump CD kick in the corner (hits twice). Sets up a nasty high-low game.
Ukyo's swallow slash also has a bug/feature in SS2 where it can be used on a back dash (that is, tapping back twice counts as jumping in the air). If you perform a db/d/df+slash while you're hopping back, Ukyo will toss the swallow under the screen and have it float back up. It's basically a normal projectile once you get the timing down, and it's pretty easy.
Ukyo is a monster against human opponents, especially when played aggressively with corner traps, since his high-low game with the swallow slash is hard to outguess if you vary things up (especially with walk-up throws...that can really make people mad). Oh yes, if you're going to use his snowfall slash (qcb+slash), only use the AB version. It's decent for block damage against someone you've just knocked over, but not much more.
Don't bother with Ukyo's f,hcf+AB POW special. It's one of the worst in the game.
Jubei is a character that depends even more on his normal moves, most obviously his B slashes (people hated him for this in arcades). His B slashes have great range and are bufferable, so a lot of low-skill Jubei players used to "turtle" by backing away as far as possible and poking with a standing or low B, and jumping backwards with an air B slash to counter any jump attacks.
If you want to learn how to play him worth a damn, learn the ranges on his B-slashes, as well as his far standing A (which is much faster than his standing B), and also memorize how to pull his counter attack (qcb, f+A) out of nowhere, in an instant. Against human players, an obvious tactic is to whiff a slash or kick, then cancel the animation in to the counter to stop a counterattack.
Jubei's special moves aren't much use outside of a combo. His standard one is a B-slash -> qcf + A. Jubei can also viciously punish big mistakes with a standing AB -> qcf + slash or f/d/df+slash (watch timing and distance). His low kicks have been slowed down from SS1, but his low D still has passable reach. His far standing C is actually a decent poke.
Jubei has a very good POW special, since he has plenty of fairly fast normal moves that can be canceled into specials/his POW special. Just like with his counter move, learn how to pull it out on a hair trigger and experiment with whiffing normal moves into the POW special. If you buffer off a very fast move like a far standing A, you can actually hit someone with it even after your previous move gets stuffed.
As for Mizuki, she's quite easily the most fair boss in any SNK game, and possibly the most fair boss in any game to date. You can definitely beat her fair and square if you're careful enough and skilled enough, though she is also, in addition to that, vulnerable to a few patterns if you get desperate. If you're having trouble with her, keepaway tactics with Jubei work just fine. I usually play Ukyo very aggressively against her, so I don't have many beginner tips for her.
If you're just desperate to see any kind of ending, pick one of the ninjas and use the shadow copy (f, hcf+button) move, then as soon as you reappear, use the f/d/df+K strike heads/shrike drop grapple. If your timing is right, and it's pretty easy, you'll reappear already grabbing her. She won't be able to do a thing to you, but it's a lot more satisfying to take her on fair and square.
So far I've only beatin the game on level 3 at the highest, used Haohmaru.
