<< Federal law only gives them either 3 or 4 days. I think it's three though. >>
Not true. Around here (Southwest PA), the former Mellon Bank placed a hold of 8 business days on all checks for a full month after the account was opened, and regardless of what bank the checks are from. The norm for banks here is to hold checks deposited into new accounts for 5 business days.
If you're strapped for cash, your best bet is to try to cash the checks at the bank they're from, and deposit only cash into your account. Once the "probation" period for the new account has passed, you can start depositing the checks without much hassle.