Why does my 23,032 byte Arduino sketch take 36.32 sec to upload via ISP to an Atmega328p on a breadboard w/code verification disabled?
ISP programmers typically default to low ISP clock rates.  Often something like 10khz, sometimes slower, probably to just work by default with very slowly clocked AVR chips.  The ISP clock rate must be about one eigth that of the AVR's clock.  For example, by defaulting to a low rate like 10Khz, the programmer will successfully communicate with an AVR clocked at 125KHz with some margin.   Around 4 KHz would work with a 32.768 KHz watch crystal.
Look in avrdude documentation for the -B option.  Note uppercase 'B', this is the option for changing the ISP speed, not lowercase -b which is for the PC to programmer (or bootloader) baud rate.   Not all programmers support -B, but many do.
UPDATE
Well, I dug around the USBtinyISP code and in avrdude and it looks like the default value for -B is 10.  So 10uS.  The way this value is used in the USBtinyISP code is for high or low period, rather than total clock period.  So it's about 20uS per bit, or 50kHz.  If that's your rate, then the plain clocking of the SPI data only accounts for about 3.7 seconds.  So that does cast doubt on this idea.
But, it still may be worth double checking that it is operating with the value 10 and not something larger.  Just to put this in perspective: the maximum -B value is apparently 250, which would result in 2kHz ISP clock rate and about a minute and a half to clock out your roughly 23 KByte.
More findings: Per byte SPI overhead
Each byte of the flash pages is being delivered into the ISP interface by way of 4-byte long SPI commands.  The firmware for the programmer has the following code in it for writing a page in its spi/main.c file where you can see it calling spi( cmd, res, 4 ) :
extern  void    usb_out ( byte_t* data, byte_t len )
{
    byte_t  i;
    uint_t  usec;
    byte_t  r;

    for ( i = 0; i &lt; len; i++ )
    {
        cmd[3] = data[i];
        spi_rw();
        cmd[0] ^= 0x60; // turn write into read
        for ( usec = 0; usec &lt; timeout; usec += 32 * sck_period )
        {   // when timeout &gt; 0, poll until byte is written
          spi( cmd, res, 4 );
            r = res[3];
            if  ( r == cmd[3] &amp;&amp; r != poll1 &amp;&amp; r != poll2 )
            {
                break;
            }
        }
    }
}

This code is used to deliver data to the flash page buffer during ISP programming.
You can see a comment in avrdude's code explaining that each byte becomes a 4-byte SPI transaction as an aid to explaining their calculation for a communications timeout with the programmer.  The following is in avrdude's usbtiny.c file for the usbtiny_paged_write function.
if (usb_out(pgm,
            function,       // Flash or EEPROM
            delay,          // How much to wait between each byte
            addr,           // Address in memory
            m-&gt;buf + addr,  // Pointer to data
            chunk,          // Number of bytes to write
            32 * PDATA(pgm)-&gt;sck_period + delay  // each byte gets turned into a
                                 // 4-byte SPI cmd  usb_out() multiplies
                                 // this per byte. Then add the cmd-delay
            ) &lt; 0) {
  return -1;
}

To be clear, these two functions have the same name but are in fact two different functions; the former running in the programmer the later is running in avrdude.
So there is in fact substantial SPI transaction overhead in just delivering data into the page buffer.  Beyond that there's a second USB and SPI transaction to commit the page buffer to flash.