Schottky Diode substitution
Most of your questions can be answered "yes", but be careful with Schottky vs. (ultra) fast diodes:

"Can I just buy the higher voltage and current rated Schottky diode and sub them for the lower rated ones?"
Should Work.

"Is the main reason for getting the exact match the cost and ability to fit?"
Some issues like the diode's capacitance have an influence on switching speed and, as a consequence, switching losses, i.e. heat generated in the diode. Try to find at least a similar device. Also, pay attention to peak values for current spikes and the like. Average current is one thing, peak current and power handling capabilities are another.

"Do I only need to match package/voltage/current?"
This is what designers do when looking for second source parts. In most cases, you will be good to go.

"Are Schottky and fast recovery the same?"
Usually, fast recovery is a label for p-intrinsic-n diodes, i.e. Si diodes, that are trimmed towards blocking fast upon being reverse biased. Schottky diodes are, really, always as fast as can be and should not be replaced with slower Si diodes, even when they're labeled "fast". The general rule is: Don't replace Schottky with Si diodes.

"Can I sub an ultra-fast for a fast recovery?"
Using an ultra-fast Si diode in place of a fast Si diode should work as far as switching losses go, but the faster switching action might cause worse electro-magnetic emissions.

"And... at the moment I need a Schottky that is in the TO220 package. Can I use two axial leads and just wire the cathodes together?"
Diodes in three-pin TO220 packages are really just two diodes. They are, however, very similar. When connected in parallel, they will share the load really well. Different packages are also often a hint towards different peak current/power handling capabilities. And, of course, thermal properties will be different. A TO220 has its own little heat sink even when mounted in free air; axial diodes don't have this nice feature.