I went through a lot of posts to figure out that, indeed, using the nearest neighbor interpolation method, in the case of a continuous raster such as a DEM, is not really a good idea. And that there is a mix between a "divinatory art" and an accumulated knowledge when it comes to applying filters.
In my case, the resulting re-projected raster is suffering some aliasing effects. I cannot explain why the repetitive pattern spacing is ~80 meters, which is not really 'near' (as in 'nearest neighbor'). And when I look closer (well, actually further), there is actually another pattern, oriented differently, with a much greater wavelength of roughly 650m.
Anyway, here are some great posts and answers out there that are worth reading imho:
Deciding what interpolation method to use for resampling raster data?
What resampling technique should be used when projecting aerial photos?
Pros and Cons of using Bilinear Interpolation and Cubic Convolution when dealing with DEMs?
Best Resampling Method for DEM reprojection in QGis
What resampling technique should be used to reproject an altitude raster?
What is the source of horizontal and vertical striping in USGS DEMs?
Why do "stripes" appear on raster?
What is Lanczos resampling useful for in a spatial context?
Based on all these, I randomly decided to chose the bilinear interpolation when reprojecting my raster DEM. I was hesitating with the cubic or cubicspline offered by the -r flag of gdalwarp as they also seem to be nice candidates. I also wanted to test the gaussian filter, but it doesn't seem to be available with gdalwarp.
The Lanczos method also looks great, but I prefer to avoid it when dealing with DEMs in order to not create altitudes that will extend out of the min-max range of the original DEM.
Here is a new line in blue, smoother and closer to the original DEM profile (green), representing the output result using the bilinear interpolation when re-projecting the DEM:
