At-will means at-will. That said, larger companies generally have policies that require documentation and a "personal improvement plan" (PIP) before termination for cause. This is mostly to provide documentation in the event of a wrongful termination suit.

However, generally if an employee is considered a serious liability (they have hurt or threatened another employee) they can be fired immediately.

Startups tend to be a little more aggressive on termination because they can't afford to pay a salary to someone for months hoping they improve.