BBTools's reformat tool does this, keeping pairs together if they are interleaved:
reformat.sh in=reads.fq.gz out=sampled.fq.gz samplereadstarget=100000000
or for reads in 2 files:
reformat.sh in1=reads1.fq.gz in2=reads2.fq.gz out=sampled1.fq.gz out2=sample2.fq.gz samplereadstarget=100000000
You can also just sample a fraction of the reads without respect to the final number, which is faster since it only needs to read the file once:
reformat.sh in=reads.fq.gz out=sampled.fq.gz samplerate=0.1
or just sample the first X reads, which is faster still:
reformat.sh in=reads.fq.gz out=sampled.fq.gz reads=100000000
Reformat is multithreaded and extremely fast.
If you want a Galaxy solution, http://toolshed.g2.bx.psu.edu/view/peterjc/sample_seqs / https://github.com/peterjc/pico_galaxy/tree/master/tools/sample_seqs
This offers non-random sampling (for reproducibility), e.g. take 12% of the sequences, or every 100th sequence.