The problem with resonators is their accuracy: At best the standard resonator will be several hundreds of ppm off from the nominal frequency, at worst it could easily be 0.1% out. It is also likely to drift horribly with varying temperature. A crystal will be a lot better: With the specified load capacitance, you can reasonably expect it to be within 20 to 30 ppm at 25 deg C room temperature. If you trim the caps you can ge:t a bit closer, but it still wont be particularly stable with respect to temperature. If the wrong caps are used with the crystal you could easily introduce another 50 ppm of frequency error. OTOH the TCXO above is specced to hold its frequency within +/-5 ppm over quite a wide temperature range. That's a worst case error of three seconds a week or to put it another way, if all your input signals are clean with sharp edges, you could build a five digit seconds and decimal fractions timer and trust the last digit.
Replacing the resonator with a crystal is relatively high risk if all you've got to do the job is an iron and the usual hand tools. Track cut and patching to fit a TCXO is a *LOT*lower risk. OTOH, if you've got a well kitted out SMD rework station with a hot air pencil, and enough practice using it, and don't mind the lower accuracy result, by all means go for swapping the resonator for a crystal and swapping its caps for the right ones to match the crystal. The only problem will be finding a small enough footprint crystal.
There's also a cheap and dirty 'no parts' (except fine magnet wire) oscillator improvement hack for genuine Arduinos that use a separate USB AVR for their host USB interface. Tack a fine modwire onto XTAL2 of the USB AVR, which has a real crystal, because of the tight frequency control reqired for USB, and onto the XTAL1 pin of the main MCU, also cutting the track from that pin from the resonator. However due to the long modwire it will probably 'pull' the crystal frequency slightly and will radiate more EMI so maybe not the best idea if you live next door to a radio ham with an interest in DXing..
For the mod you really want good groundplane where you are going to put the TCXO, so you can tie its Gnd to board ground with a very short wire, and placed well away from heat sources like regulators and the MCU itself. The area under the G of the yellow GND you added to the image looks like the best choice. You've already identified the best place to pick up 3.3V, and 5V if you need it.
That board layout is a bit different to the one I was working from for the instructions. I'd make the track cuts where they are still straight and parallel coming from the MCU XTAL pins just above where they bend 45 deg to the left towards the resonator and just below where the adjacent track bends to the right. That's where IMHO you've got the best chance of not nicking an adjacent track with the scalpel blade. Alternatively find the silk screened "C5" and "C6" of the resonator caps, and cut the tracks on a line between the right edges of those silkscreened markings. That gives you a wider spacing between them if you ever have to undo the mod, so less fiddly to bridge the cuts.
When you are bypassing tiny little parts you need tiny little capacitors. If you can find a N.O.S 5V metal can DIL14 (corner pins only) 16MHz TCXO with glass frit hermetic seals on three of its four legs and the Gnd leg welded direct to the can, then you can use your disk ceramic 100nF cap reasonably safely, but if you used it with a SMD TCXO and it got bumped you''d be risking ripping the 'pin' pads off the SMD package. For the SMD TCXOs you need SMD caps just to get ones that will fit conveniently across the pins that need decoupling, and as the pin pitch shrinks you need to go increasingly towards the 'invisible fly sh-t' end of the SMD passives size range. When you are right down at the limit of what an expert with steady hands can deadbug without needing a micromanipulator, a through hole passive would have leads considerably larger diameter than the pin pitch so would be even more of a nightmare to use than the SMD fly sh-t. Its really not hard to put one in place, tombstoned or flat. Tin the pad its got to go on, (one only if mounting flat). get a trace of paste flux on the corresponding end of the part., place it with tweezers and reheat the tinned pad to make the joint. Then hold flat ones down with a toothpick or small flat jeweller's screwdriver while you solder the other end. Tombstoned ones are a bit trickier, but you've got the benefit of a lot of groundplane area at the bottom end, so if you are quick and have the top end wire or pin in exactly the right place you can solder it without remelting the bottom joint. If you dwell too long. it *WILL* remelt then stick to your bit (and the same if you slip while holding a flat one down). Don't try to retrieve small passives stuck on your bit - just curse eloquently, wipe them off, clean up one pad with braid if the SMD part needs to go flat, then get a fresh one off the reel or cut tape and try again. A good nights sleep and 24H without coffee or other high caffeine drinks helps most SMD novices considerably, as does obscenely bright easily positionable bench task lighting. If you need sunglasses because of the glare, its probably a little too bright!
The first TCXO you found was a good convenient match to the pin order and spacing of the suggested 74LVC1T45 level shifter. so although its tiny they were a good pair. If you are trying to go direct to XTAL1 with a 3.3V signal level, it may or may not work. The MCU datasheet says 'don't count on it' but practical experience says the odds are in your favour. The larger TCXO will definitely be easier to deadbug. It has a control voltage input on 'pin' pad 1 for +/-5 PPM of frequency trim, which could be useful if you become a 'time-nut' but it says it can be left N/C so you can ignore it for now*. Its decoupling cap would probably be best fitted diagonally across 'pin' pads 2 and 4, again before attaching any wires. Don't be scared of working with tiny parts. Press the TCXO on some thin double sided sticky tape, and you can get the cap and wires attached to it working on your bench before you even touch the Arduino board, so if that doesn't go well all you are out is the cost of the TCXO and the 10nF cap. Once you've got the wires on and its looking like a crippled spider, you can pry it off the tape with the tip of your scalpel blade and transplant it to its final position on a drop of glue on the board.
* Future Time nuttery could include ovenizing the TCXO in a little copper foil 'jacket' inside an expanded polystyrene block, itself with an aluminum foil 'jacket', with a small power transistor to heat it and a DS18S20 digital temperature sensor for the Arduino to read and control the oven temperature, a high precision DAC to control the pin 1 voltage to trim the TCXO, and a GPS module with one PPS output pulse so the Arduino has a long-term stable reference to trim the TCXO to. That's the basics of a budget GPSDO, and could easily let you get a reliable sixth digit of accuracy. Obviously you'd need to put all the gubbins on a proto shield and run a modwire down to the Arduino XTAL1 track. (Or if you are feeling really too clever, desolder the resonator and caps and solder a pogo pin to the underside of the protoshield so it lands on an XTAL1 pad!)