The remaining difference in speed is most likely due to strlen of "foo" being recomputed every time in the inner loop (i.e. the zero in newSVpv(foo, 0) ).

Precomputing it once (as Perl can do too, because the "foo" in "foo" x $n_cols is by definition fix) — i.e.

SV *make_aoa_c( int n_rows, int n_cols ) {
  int i, j;
  char *foo = "foo";
  AV *table = newAV();
  AV *row;
  int len = strlen(foo);
  av_extend(table, n_rows-1);
  
  for ( i = 0; i < n_rows; ++i ) {
    row = newAV();
    av_extend(row, n_cols-1);
    for ( j = 0; j < n_cols; ++j ) {
      av_push( row, newSVpv( foo, len ) );  // or newSVpvn(...)
    }
    av_push( table, newRV_noinc( row ) );
  }

  return newRV_noinc( table );
}
[download]

makes any XS vs. Perl speed difference go away (or at least statistically insignificant).

(Without this optimisation I did observe a small, but consistent difference — approx. 5% on average.)