Where do startups store millions of dollars of capital?

Just about everywhere you can store money without much risk today has very low yields. In general, if getting an entra 0.5% yield on your cash is really meaningful, you should have millions of dollars laying around.

I know of a regional credit union offers 1% interest on business checking accounts with over $1mm which is pretty good compared to rolling T-Bills.

Not the smartest but a safe way: Rolling 3 month T-bills at your friendly banker (in book entry form, i.e., in your name). You can get more clever (and more return on your capital) if you are willing to take some risk. Just remember that risk works both ways.

Nothing wrong with checking account.

When you think about "return on capital", do not forget "return of capital".