TL;DR: Use new SecureRandom() when you're not sure and let the system figure it out. Possibly use SecureRandom.getInstanceStrong() for long term key generation.
Do not expect a random number generator to generate a specific output sequence within a runtime application, not even if you seed it yourself.
With random number generators it is always hard to say which is best. Linux and most Unixes have a pretty well thought out random number generator, so it doesn't hurt to use /dev/random or /dev/urandom, i.e. "NativePRNG". Problem with using /dev/random is that it blocks until enough entropy is available. So I would advice against it unless you've got some special requirements with regards to key generation.
"SHA1PRNG" uses a hash function and a counter, together with a seed. The algorithm is relatively simple, but it hasn't been described well. It is generally thought of to be secure. As it only seeds from one of the system generators during startup and therefore requires fewer calls to the kernel it is likely to be less resource intensive - on my system it runs about 9 times faster than the "NativePRNG" (which is configured to use /dev/urandom). Both seem to tax only one core of my dual core Ubuntu laptop (at a time, it frequently switched from one core to another, that's probably kernel scheduling that's which is to blame). If you need high performance, choose this one, especially if the /dev/urandom device is slow on the specific system configuration.
Note that the "SHA1PRNG" present in the retired Apache Harmony implementation is different from the one in the SUN provider (used by Oracle in the standard Java SE implementation). The version within Jakarta was used in older versions of Android as well. Although I haven't been able to do a full review, it doesn't look to be very secure.
EDIT: and I wasn't half wrong about this, SHA1PRNG has been shown not to be pseudo-random for versions < 4.2.2 and more here.
Beware that "SHA1PRNG" is not an implementation requirement for Java SE. On most runtimes it will be present, but directly referencing it from code will make your code less portable.
Nowadays (Java 9 onwards) the OpenJDK and Oracle JDK also contain multiple implementations that are simply called "DRBG". This implements a list of Dynamic Random Bit Generators specified by NIST in SP-108. These are not Java implementation requirements either. They could however be used if a FIPS compliant random number generator is required.
However, they do not change the recommendations here; if the developers thought that these were better than the default implementation then they would simply have made it the default. The contract of SecureRandom doesn't change: it is simply required to generate random numbers. Changes to the default algorithm have already been made in the past.
In general it's not a good idea to require a specific provider either. Specifying a provider may hurt interoperability; not every Java runtime may have access to the SUN provider for instance - Android certainly hasn't. It also makes your application less flexible at runtime, i.e. you cannot put a provider higher in the list and use that instead.
So only indicate a provider if you are dependent on one of the features that it supplies. For instance, you might want to specify a provider if you have a specific hardware device that generates the randoms, or a cryptographic library that has been FIPS certified. It's probably a good idea to make the algorithm/provider a configuration option for your application if you have to specify a provider.
The idea of not specifying a provider is also present in this Android developer Security Blog.
So try and refrain from choosing any specific random generator. Instead, simply go for the empty argument constructor: new SecureRandom() and let the system choose the best random number generator. It is possible to use the new configurable SecureRandom.getInstanceStrong() in Java 8 and higher if you have any specific requirements for e.g. long term key generation.
Don't cache instances of SecureRandom, just let them seed themselves initially and let the VM handle them. I did not see a noticeable difference in operation.
When not to use SecureRandom at all:
As a general warning I strongly advice against using the random number generator for anything other than random number generation. Even if you can seed it yourself and even if you choose Sun's SHA1PRNG, don't count on being able to extract the same sequence of random numbers from the random number generator. So do not use it for key derivation from passwords, to name one example.
If you do require a repeating sequence then use a stream cipher and use the seed information for the key and IV. Encrypt plaintext consisting of zeros to retrieve the key stream of pseudo random values. Alternatively you could use a extendable-output function (XOF) such as SHAKE128 or SHAKE256 (where available).
You may want to consider a different, non-secure random number generator instead of SecureRandom if the available RNG's deliver insufficient performance and if security is not an issue. No SecureRandom implementation will be as fast as non secure random number generators such as the Mersenne Twister algorithm or the algorithm implemented by the Random class. Those have been optimized for simplicity and speed rather than security.
It is possible to extend the SecureRandom class and insert a deterministic, seeded random implementation into a library call. That way the library retrieves a pseudo random number generator with well defined output. It should however be noted that the random number generator may be used in different ways by algorithms. E.g. RSA may switch to a better optimized way of finding primes and DES keys may be generated with adjusted or directly calculated parity bits.
