So when does everyone recommend applying for jobs? I don't want my husband to apply too early, because sometimes these things move quickly, and it would be heart breaking to get a job offer and then have to say, oh btw, I haven't received my EAD/GC yet... and then it is a lost opportunity. Based on our estimated timeline on VJ, we should have the EAD about 4 weeks from now. I was thinking to start applying another 2 weeks, what did you all do?

I would wait until you get the EAD approval email.

in my industry (Software development), the interview process generally takes a month, from first contact to offfer. Then, when they ask you when you can start, you can usually expect to be able to work out your notice period (generally 1 month). So applying simple arithmetic gives me a time frame of about 2 months prior to receiving EAD.

But then it depends on your husband's industry.

I also suggest waiting until the EAD has been approved (they'll notify you via e-mail or you can see the update on-line). Sometimes you apply, have the interview in a day or two, and then start working immediately (that was my hubby's case) so it's better to know you're authorized to work.