Arduino-based mains frequency monitor
I understand Arduino should be somewhat simpler [than PIC].

The whole Arduino platform (boards, core library and IDE) makes it super
easy to get started and do simple things. However, if you want to
“push the limits” and use the full potential of the MCU, you may have to
dig into low-level programming, and this has a steep learning curve.

The 250V mains will be half-rectified with an IN4004 (?) transistor
(together with a 1K resistor and 0.22uF cap), and that will go into a
4N35 optocoupler.

1 kΩ seems way too low to me: your resistor will dissipate on
average 31 W, and it will burn unless it is a heavy-duty power
resistor. You should choose a resistor that limits the current to a
value low enough to avoid overheating, but still high enough to reliably
turn on the optocoupler. If these two constraints end up being
incompatible, you will need a step-down transformer in addition to (not
instead of) the optocoupler.

A digital (?) GPIO pin from the Arudino goes into the base of the 4N35
and emitter goes to GND.

The base of the optocoupler is typically left floating. You connect the
Arduino input to the collector, using either the internal or an external
pullup resistor, and you ground the emitter.


I believe the Arduino can reliably be powered by USB.


Yes, powering through USB is fine. The Arduino itself draws very little
power. Only when it is powering something else you may worry about
power limits. Here it would seem your Arduino will only be sourcing a
very small amount of current into the output transistor of your
optocoupler, so you will be fine.


How stable is the clock on the Arduino?


Terrible. Most Arduinos are clocked off a ceramic resonator. These
are typically specified with 0.5% frequency tolerance, but their
frequency is constantly fluctuating, and is also strongly dependent on
ambient temperature. This makes those Arduinos grossly unsuited for any
job requiring precise timings. I would recommend you get an Arduino
sporting a real quartz crystal, like the Leonardo or the Micro. A quartz
crystal can be quite inaccurate, but at least its frequency is stable.
It's orders of magnitude more stable than a ceramic resonator. C.f.
for example this article about the Arduino clock frequency
accuracy.


I presume I'll need to debounce the result from the optocoupler?


If the capacitor after your half-wave rectifier is well dimensioned,
your signal should be clean and not need debouncing. The Arduino digital
inputs all have Schmitt triggers which clean up the input noise as
long as it is not excessive. If you really need debouncing (check with a
scope if you can), well... there are no provisions for doing so in the
Arduino core library, but there is a Debounce tutorial among the
examples shipped with the Arduino IDE, and there are a few third party
debounce libraries floating around the Web.


How simple is it to write some software (in C#) that will recognise
the Arduino connected via USB, and communicate with that device in
particular?


As stated in other answers, your Arduino will be seen by your computer
as a virtual serial port. I don't know C#, but any decent programming
language should allow you to easily read data from a serial port.
Measuring method:
You will time one or several periods of the input signal. There are
several ways of doing so. In roughly increasing order of complexity and
accuracy:

You continuously monitor the digital input, in a loop, and whenever
you see a transition from LOW to HIGH you record the current time
using micros().

You use an interrupt pin as the input and you have the interrupt
handler record the time with micros().

You use the input capture facility of your 16-bit timer running at
the full CPU speed.


The methods using micros() have a resolution of 4 µs. Both will
give you some software-induced jitter because they depend on the timing
of your program execution. The advice given by GuitarPicker: “Keep your
code predictable, using as few conditional branches as possible that
might alter how long your code takes to run each cycle” is relevant only
to the first method. The interrupt method is immune to your main loop
timing, but it is still affected by the CPU processing other interrupts.
The input capture method will give you single-cycle resolution and
accuracy, with zero software-induced jitter. That would be my first
choice, but it requires digging into the MCU datasheet and doing some
low-level programming.

Addendum: Here are some tentative answers to a comment posted by
Ozzah to his own question:

I probably want 4 decimal places if possible.

If you want 10−4 absolute accuracy, you may need to
calibrate your clock, even if it is a crystal. If you only require
10−4 stability (variations of the frequency), then even a
ceramic resonator may be (barely) up to the task, if you don't mind
recalibrating it every few weeks, and assuming your indoor temperature
doesn't vary by more than ≈ 10°C.

I want the highest resolution and best tolerance possible.

Then a quartz crystal is definitely a plus. It's roughly 100 times
more stable than the ceramic resonator.
But if you really want the “best”, you may as well follow Milliways'
advice and get a GPS reference. Some options, in increasing order of
price and accuracy:

A simple GPS module for the Arduino. Make sure you get one with a
1PPS output (a “one pulse per second” reference signal). You may want
an external antenna for better reception.
A GPSDO (GPS disciplined oscillator). This is typically a lab-grade
frequency standard consisting of an OCXO (oven-controlled crystal
oscillator) disciplined by a feedback loop into tracking GPS time. It
gives the same long-term stability as the simple GPS module but has
far better short-term stability.
A rubidium-based GPSDO. This is similar to the above but has also a
rubidium atomic frequency reference. Still better short-term
stability. Now we are talking about stabilities in the
10−11 to 10−12 range. Provably overkill for
your use case.

From the software point of view, I would recommend you start with the
interrupt method, just to get a prototype working easily, and then go to
the input capture method, as it will give you the best accuracy. It
should be possible to be cycle-accurate with the interrupt method, but
that would require some non-trivial tweaks.
Note also that the Arduinos based on the ATmega32U4 (Leonardo and Micro
at least) have two 16-bit timers with input capture capability. You
can then time both the mains signal and a 1PPS reference in parallel. If
your Arduino has only one 16-bit timer (like the Nano), you would have
to time one of the signals with the interrupt method.

I'm trying to find a way to determine which Arduino boards use
crystals for the MCU clock and which use ceramic resonators. From what
I can see, they all have a crystal, but presumably that's for the USB
interface?

Yes, the USB/serial interface is clocked off a crystal more often than
the main MCU. The Arduinos that do not have a separate USB/serial
bridge (like those based on the ATmega32U4) seem to have the main MCU
clocked off a crystal.

How can I get a list of Arduinos that use crystals?

It's often stated in the product page. E.g., the page of the Arduino
Micro states
(emphasis mine): “It has 20 digital input/output pins (of which 7 can be
used as PWM outputs and 12 as analog inputs), a 16 MHz crystal
oscillator, a micro USB connection, an ICSP header, and a reset
button.”
Arguably, the info is not very prominent, and a compiled list would be
useful. I think this could be a very good question to ask in this site.