Against the rebellion problem, I try to tech up to a religious building and make 200 peasants. It seems that loyalty depends on the number of units in a province (and not on the unit type). 2 sets of peasants cost 100 to make and 24 maintenance I think, so you'll get that back in 1 year. If this is still not enough, lower the tax a bit (I mean, if you have 60% of the map, you have bulking treasures too, at least I always have).

And I always have 1 or 2 outdated armies moving behind my main force which stay in conquered provinces for a while to get people used to me.

As to sea battles, try to mix fleets; put in some fast ones and some slow ones and such. Usually you'll have no problem then.

@ Czar:
While keeping your king away from battle may give some advantage, it will also diminish the royal line bit by bit. They won't get alot of command if daddy is a chicken and won't fight, nor much dread for that matter. Besides, the royal generals are a free way to get high command generals (you don't need to train them in battle since they get characterics much like their father, so if he has alot of command, good bet his son will be good too when he's born, without having even won 1 battle yet!)
I prefer to make to work on the royal line... this is turn helps with loyalty too (just kill some prisoners every once in a while and he'll get dread-related V&V)