@chingc,

For example, if I have 20 total jobs and max-parallel is 5, GitHub Actions will start 5 jobs but will not start more until all 5 are complete.

I also tested this with GitHub-hosted runners and self-hosted runners, however I did not reproduce the issue likes as you mentioned.
In my test, after one job in a batch was completed, a queued job would start, it did not wait other jobs in that batch to be completed, although there may be some delay to start the queued job after the previous job completed.

I noticed this description in the docs:

By default, GitHub will maximize the number of jobs run in parallel depending on the available runners on GitHub-hosted virtual machines.

When using GitHub-hosted runners, there may be some usage limits.
If you are using GitHub-hosted runners in your matrix, you can try to use some self-hosted runners to see if the issue still exists.