Diode package selection in flyback circuit for a relay
1: Your guess is correct, but I would just use a common 1N400x diode. They're dirt cheap and have reverse breakdown voltages measured in the hundreds or thousands of volts.

2: As for the package, the only thing that really affects what package you use is power concerns. If you need to dissipate a huge amount of power (which you don't), you would go with a TO-220 with a heatsink. Moderate power, a D²PAK would work well. But this isn't going to need that much power dissipation, because the current is going to be in very short pulses when the relay turns off, so you can probably just use whatever package you want, as long as the diode inside is rated for the current you need.

If you want a more precise answer, look for thermal resistance specifications; there should be a junction-to-ambient thermal resistance spec measured in °C/W, which tells you how much hotter than the surroundings you can expect the junction to get, and you can then look at the device's maximum temperature specs to know that it'll work.