Which phone do you recommend going with it?

GrapheneOS supports Google Pixel 2 and later, but only Google Pixel 3 and later are currently supported by vendor security updates:

https://grapheneos.org/releases

All Google Pixel phones released to date receive vendor security updates for 3 years after the release date: https://support.google.com/pixelphone/answer/4457705

A Pixel 4a ($349 new) would cover you until August 2023, and a Pixel 4a (5G) ($499 new) would cover you until November 2023 with better performance. The Pixel 5 is not a particularly good value for the price. Used Pixel 3, 3a, and 4 devices (along with their XL counterparts) are less expensive options with vendor support timeframes that expire sooner. The Pixel 3 and 4 (non-XL) models have poor battery life, so choose an XL model if you opt for either of those.

Thanks! Unfortunately as you note recentish Pixels are not all that great, at least last time I checked. But perhaps at the next release I might change back (I really want to), if it’s suitable. But it is a real shame that other manufacturers make it very hard to replace the OS. The one other phone family I heard great things about is the One Plus, but they may also contain firmware that gets nulled.