Hi Guillo -
Welcome to PhotoshopGurus.com. Glad to have you.
First, a few questions / comments:
1. The original, full size (ie, 5000 x 3750 px) image is offered by psdgraphics.com and can be found
HERE. From what you have said, it appears that your use is within their
Terms of Use. Have you read them? Do you agree?
2. In your original post, you say that you eventually want to have a square print, 96 x 96 inches. I suggest that instead, you leave the aspect ratio unchanged because this will improve the look of the final product. There are two ways to change the aspect ratio of an image: (a) You can crop this image horizontally, but, unfortunately, this will cut off some of the darker, visually interesting parts of the design that are in the corners; or, (b) You can down-sample the image along the horizontal axis, and then up-sample it to the desired final resolution, but then the image will appear distorted (squished in one direction / elongated in the other). Because of this, I strongly urge you to print this image at the current aspect ratio, or find another image that started life as a square.
3. If one looks at the image metadata, you will see that it doesn't contain any tag for a specific color space, eg, sRGB, AdobeRGB, ProPhotoRGB. In the absence of such a tag, browsers, image viewing software and printers will assume that it's an sRGB image. This is why the colors in the upper RH corner seem to stop at orange instead of red. I will bet you that this image was actually constructed in a wider gamut space than sRGB and using reds. When I worked on the image, I immediately assigned it to ProFotoRGB and the reds were just beautiful on my wide gamut, hardware calibrated monitor. When I was done with my manipulations and went to save it as a JPG for printing, I then converted my final ProFoto version into AdobeRGB because most good printers can handle that color space and it doesn't wash out as much of the differences between similar reds as sRGB.
4. Prints that are as large as you want are almost always viewed from several feet away so that the viewer can take in the whole print at once, without too much motion of their head. They are almost never viewed from the same distances that one would view a little 4x6" or 8x10" print. This is extremely fortunate because it means that one can usually get away with 100 ppi at these larger sizes, not the usual 250-300 ppi that one needs for smaller prints. This means that starting with the 5kpx wide version available online (ie, not the 3500px version you posted), one only needs to up-rez it to 12.8 kpx wide to get to a print that will be 96 inches in the short dimension (ie, ready to be cropped or resized in 1 direction).
5. As you have discovered, even the quality of the original 5kpx wide image on their website is not the best, particularly, along each of the boundary lines in the image where two different colors are adjacent. By far, the best way to do this job would be to have the image in a vector graphics form (eg, *.ai) so that it could be resized to any dimensions without loss of quality. Lacking that, the next best way would be to take the image into Adobe Illustrator, use live trace on it to get started, and then tweak all the paths that it finds, and add paths that it didn't find (eg, between two similar colors). It would take quite a bit of work to do this correctly. Perhaps someone will be kind enough to do this for you for free. However, if you really demand the highest quality, we could put your request into our fee-for-service section, and the chances are good that someone will pick up the job for a very modest fee.
6. The best I could do in the limited time I wanted to devote to this project was to do it the way you envisioned (ie, in PS with a rasterized image), but I incorporated some visual tricks to make the boundaries between colors look more well defined. My final result is 128" x 96" @ 100ppi in Adobe RGB. With this, you can then easily either crop that or down-rez (aka, resample) the long dimension back to 96" if you insist on a square format. Don't forget that an Adobe RGB image will not show the correct colors on much current image viewing software (viewing it in Photoshop will be fine), and can't display properly unless you have a monitor whose gamut is that wide, BUT a good printer should be able to handle AdobeRGB with no problem at all.
Anyway, see what you think.
Tom M