Thanks to the related section, I came across @Kezhas answer here - who seemed to be suffering experiencing the same issue as me.

Essentially a QApplication.instance().processEvents() is required after adding the layer (and before setting the CRS), as follows:

# Create new project
iface.newProject(promptToSaveFlag=False)
project = QgsProject.instance()

# Create map tile layer (which by default uses EPSG:3857)
map_uri = 'type=xyz&url=http://a.tile.openstreetmap.org/{z}/{x}/{y}.png'
raster_layer = QgsRasterLayer(map_uri, 'openstreetmap.org', 'wms')
if raster_layer.isValid():
    project.addMapLayer(raster_layer)

# Process events before setting CRS
QApplication.instance().processEvents()

# Set CRS to EPSG:4326
project.setCrs(QgsCoordinateReferenceSystem('EPSG:4326'))

EDIT: So it turns out using QApplication.instance().processEvents() could well be dangerous (and quite possibly evil!)

It seems using QTimer.singleShot() is a better approach.

As such, I adopted my code below, which now works as expected.

def reset_and_load()
    # Create new project
    iface.newProject(promptToSaveFlag=False)
    project = QgsProject.instance()
    
    # Create map tile layer (which by default uses EPSG:3857)
    map_uri = 'type=xyz&url=http://a.tile.openstreetmap.org/{z}/{x}/{y}.png'
    raster_layer = QgsRasterLayer(map_uri, 'openstreetmap.org', 'wms')
    if raster_layer.isValid():
        project.addMapLayer(raster_layer)

    # Call QTimer with 10ms delay (adjust to suit) to set CRS
    QTimer.singleShot(10, set_project_crs)


def set_project_crs():
    # Set CRS to EPSG:4326
    QgsProject.instance().setCrs(QgsCoordinateReferenceSystem('EPSG:4326'))

For further reading see also the GIS answer here, and comments here.

Warning: Answer/code below is being left because it works, though could be dangerous - see edit above

Thanks to the related section, I came across @Kezhas answer here - who seemed to be suffering experiencing the same issue as me.

Essentially a QApplication.instance().processEvents() is required after adding the layer (and before setting the CRS), as follows:

# Create new project
iface.newProject(promptToSaveFlag=False)
project = QgsProject.instance()

# Create map tile layer (which by default uses EPSG:3857)
map_uri = 'type=xyz&url=http://a.tile.openstreetmap.org/{z}/{x}/{y}.png'
raster_layer = QgsRasterLayer(map_uri, 'openstreetmap.org', 'wms')
if raster_layer.isValid():
    project.addMapLayer(raster_layer)

# Process events before setting CRS - Use at own risk (see above)!
QApplication.instance().processEvents()

# Set CRS to EPSG:4326
project.setCrs(QgsCoordinateReferenceSystem('EPSG:4326'))