hey jacob
from my experience in the north where you are already looking, you can pretty much throw a stone and find a great place to kite. it really depends on an honest look at your level to determine the best place for you to start imo. if you are really new, contacting a center like bear suggests would be ideal and then getting a solid week or two of not just instruction but also folks looking out for you as you progress away from lessons.
if you are ok/self sufficient but looking for lessons to improve, you could start in cumbuco and get lessons there and then hit a multitude of spots on the way to guajiru or jericoacoara and really see a bit of the countryside. the downwinder packages along there are pretty rad. cumbuco was probably the best place for a bit of social life as well (apart from jeri).
personally, i really liked icarai de amontada though the area is probably lesser known amongst the crew that like butter flat lagoons to ah, demonstrate, their prowess. but the town had a nice vibe too (some cool beach resorts there too if you want a night or 2 to impress the missus - can't remember the name of the one around the bay a bit, but was gold). also paracuru had some ok waves while i was there and a good kite center and set up but you had to drive out to the kite spot.
on crowds - don't expect to kite alone in the lagoons etc - it can be really crowded, especially on weekends when the city crew do trips out. the local guys absolute tear too, so give yourself plenty of time/room wherever you go. but if you are confident in ocean, there is isolation in abundance along the 500km or so of coast that i can remember.
have a great trip mate, enjoy
ps. cachaca cachaca cachaca - thank god winds come up in the afternoons!!!