-You can file Form I-539 for change of your status from H-1b to H4 before or right after you are laid off.
2.After I lose my job, am I out of status while waiting for it (H1-B to H4) to be approved?
-You are legally present during this period.
3. What is the best solution, if I'm agressively looking for a job? Change status now or hold a little bit?
-Change your status when you lose your job.
4. Would my next employer like to start me from H1-B transfer, or a new petition and change my status from H4 to H1-B?
-After you find a new job, just change your H4 back to H-1b status again.