Some things we learned:
1. Apple will not help figure out anything that happened. They won't even tell us the vector by which the password was changed, though we think it was the security questions.
Apple has a "devices" feature that is neat and will show you currently signed in iCloud devices and a button to sign all other web sessions out. Unlike Google, however, you have no access to IP addresses for the devices, and no access to see what or how many web clients are logged in whatsoever.
2. As long as you don't fail the security questions 3 times in a row you can just sign out and sign back in again. Apple will keep letting you try and won't even give you the same questions necessarily (they provide 2 out of 3).
Google no longer allows password resets with security questions.
3. Don't get hacked after 10 PM pacific. There is literally nothing Apple will be able to do until the next day Apple Care is open.
Google and Facebook both have fairly awesome workflows for getting your stuff back and in order. They aren't perfect but facebook.com/hacked is amazing and will even hunt for recent vandalism on your account. Google has a similar process that walks you through it and checks for open "back doors", like someone setting your gmail to forward to them before they log out.
4. Apple has 2 different, additional security options you can enable. Incredibly, they are named "two-step" and "two-factor" authentication and they are different in that one uses SMS only and one uses trusted devices.
5. If you have a habit of taking photos of important documents like 1099s or ID to send them to someone quickly, you may want to stop.
6. It is nice knowing that past text messages were not likely compromised.