Your Java engine's speed seems pretty reasonable to me on one CPU.

There are various ways engines count nodes and report nps, and many ways to report depth also.
In the end, nps and depth are really only meaningful to you once you develop a sense of how your engine performs.

One way is to simply ...

If you have not looked here yet, there is a huge amount of info

https://www.chessprogramming.org/Main_Page

The idea is that if the current side to move cannot improve it's score by making two moves in a row, then things must be really bad, so this line gets pruned.

Also, follow the links for the zero window bounds or search to understand the "null window" for alpha and beta.

For an example, suggest ...

Yes.
But every engine is different.
I tried Crafty's approach in Tinker and it did not seem to help.
So, again, try it and see.

An interesting idea.
The only way to really know is to play some matches.
This is particularly the case for search-related changes, where speed and depth differences do not always result in better play.
For evaluation changes, generally faster is typically better.

All engines with parallel search have some randomness.
All timed searches also have randomness.

Single thread engines searching a fixed number of nodes should always be the same.

I don't think randomness has anything to do with finding mates.
There are engines like matefinder that are coded ...

The FENs are easy. Each of the 4 positions in a set should have the same static evaluation score, or there is a bug in your eval code.

Q-search is needed because the engine will play terrible chess if you leave pieces hanging to be captured at the leaves of the regular search. Q-search follows ...

A good place to start:

http://chessprogramming.wikispaces.com/Evaluation

Sorry, I meant letting the compiler unroll the loops Debug v Release.

And, then compiler unrolled Release v manually unrolled Release for same Perft depths.