Do breaker trip curves ever begin BEFORE the load printed on the breaker handle?
First, I don't know about those charts.  (actually I do know; I browsed them on Friday as part of other research; but you need to look at context and notice they are and NOT for breakers in your home.) 

The only trip curve that matters to you is the one published in the catalog for the breakers that are in your own panel. 

It's possible to get breakers with trip curves like that, but they don't fit your HOMeline panel lol, and they don't cost 5 dollars!   They do, however, let you deep-dive into the arcane subject of breaker selective coordination, i.e. the fine art of reliably and reproducibly having the local breaker at the hydraulic press trip before the feed breaker back at the main panel 3 floors down.


  For instance, if I put exactly 20 amps of electric heat on a 20 amp breaker, using conduit and all quality components, should I expect that to trip at some point, or not?


They don't guarantee it won't.  In fact, since the thermal trip mechanism will be in play, it will matter greatly whether the Arizona sun is blasting on your outdoor panel vs whether it's buried in a snowdrift. 


  19 amps I would expect to trip never. 21 amps I would expect to trip 'eventually'. 10000 amps (dead short) should trip more or less instantly. Correct me if I'm wrong.


I wouldn't expect that kind of precision for $5. 


  Do branch circuit breakers work the same as mains in this regard?


My view is that, if anything, main breakers are more tolerant (to the vexation of anyone trying to use a main-breaker subpanel as a disconnect with hopes that the local breaker trips first)... However, they are cut from the same basic stock.  In fact, when a "main breaker" is actually a backfed breaker, they are the same basic stock.