**Short answer:**

Try

	'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
	'format' => '?paged=%#%',

**Long answer:**

I took a look at the `paginate_links()` source code ([v3.5.1][1]) and there is this line ([#][2])

    $link = str_replace('%_%', 1 == $n ? '' : $format, $base);

that is giving you the empty first page link. 

With your setup you have `$base = "%_%"` and `$format = "http://example.com/page/%#%/"` so this becomes:

    $link = str_replace('%_%', 1 == $n ? '' : "http://example.com/page/%#%/", "%_%");

where we have two cases:

    n=1:     $link = str_replace('%_%', '', "%_%");

    n>1:     $link = str_replace('%_%', "http://example.com/page/%#%/", "%_%");

and after the replacement:

    n=1:     $link = '';

    n>1:     $link = "http://example.com/page/%#%/";


Here is an example of the output from `paginate_links()`:

    <ul class='page-numbers'>
    	<li><a class="prev page-numbers" href="http://example.com/page/2/">&laquo; Previous</a></li>
    	<li><a class='page-numbers' href=''>1</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/2/'>2</a></li>
    	<li><span class='page-numbers current'>3</span></li>
    	<li><a class='page-numbers' href='http://example.com/page/4/'>4</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/5/'>5</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/6/'>6</a></li>
    	<li><a class="next page-numbers" href="http://example.com/page/4/">Next &raquo;</a></li>
    </ul>

If you use instead ([#][3]): 

	'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
	'format' => '?paged=%#%',

then you get:

    $link = str_replace('%_%', 1 == $n ? '' : "?paged=%#%", "http://example.com/page/%#%");	

Since no replacement will take place

    $link = "http://example.com/page/%#%";	

in both cases (n=1 and n>1), you will get a non empty first page link and the the output of `paginate_links()` will be something like:

    <ul class='page-numbers'>
    	<li><a class="prev page-numbers" href="http://example.com/page/2/">&laquo; Previous</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/1/'>1</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/2/'>2</a></li>
    	<li><span class='page-numbers current'>3</span></li>
    	<li><a class='page-numbers' href='http://example.com/page/4/'>4</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/5/'>5</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/6/'>6</a></li>
    	<li><a class="next page-numbers" href="http://example.com/page/4/">Next &raquo;</a></li>
    </ul>
	
To have a non empty first page link it looks like  `$format` can be any string as long as `$base` doesn't include the string `"%_%"`, i.e. these should work fine:

    'format' => '?paged=%#%',
    'format' => 'page/%#%',
    'format' => 'asdfasdfasdfasdfasdf',

If you don't use permalinks, then the example in ([#][3]) will also give you non empty first page link since

    $link = str_replace('%_%', 1 == $n ? '' : "?paged=%#%", "http://example.com/?paged=%#%");	

with replacements.


  [1]: http://core.trac.wordpress.org/browser/tags/3.5.1/wp-includes/general-template.php#L1922
  [2]: http://core.trac.wordpress.org/browser/tags/3.5.1/wp-includes/general-template.php#L1970
  [3]: http://codex.wordpress.org/Function_Reference/paginate_links#Examples