I thoroughly enjoyed my visit to Madang last March. It was quite beautiful, the weather was lovely, and there are a couple of resorts that sound perfect for your needs. It is the "reasonably priced" part that is so problematic here in PNG, at least for me (I'm from the USA).
Alotau is on my destination list for November, so I don't know how it compares.
Good luck!
