- Show/Hide stuff on VF page with AJAX
Basically the rule is to always have the rerendered region bigger than the stuff that has conditional visibility. If they are the same size, you may have the problem of things unable to become visible, because the rerendering never works due to the id not being there the first place.
- Create checkbox list on the fly
This is common for searching-then-processing. However the approach isn't necessary for simple situations where you just need simple labels. You can just use the built-in SelectOption class and <apex:selectCheckboxes>.