Bear in mind that Shadow of the Colossus was first released in 2005 to a very unsuspecting public.
As for 'how' and 'why' it became special in my books, let me try and sum up how I first experienced the game on a Saturday night in 2005: At first, it felt like Zelda for grownups, then the surreal, mostly empty landscape evoked feelings of isolation and angst we've first (and probably last) gotten in, say, Silent Hill on PSX. The minimalist approach made everything you got so much more special, like that horse of yours... and the colossi, of course. Also, don't forget your hero player character starts out with nothing but a horse, a stolen sword with seemingly magical powers and lugging around the dead body of his beloved lady of choice. That's not exactly Dora the Explorer stuff.
The first time you encounter a colossus, or some of the colossi, tends to feel like a special occasion, and that - lasting - feeling of amazement and wonder was, and is, a true achievement for any medium. I remember it also didn't quite feel good to kill that huge and special creature. It did not feel instantly rewarding like, say, hunting, or jumping on a goomba, or taking out an enemy soldier with a headshot. It was hard work, and in the end, something amazing which you never quite got to grasp in full was dead. This is, of course, a personal experience, the quality of which depends largely of your own thoughts and notions and the books/stories/fairy tales/movies you've consumed up to this point. Once you reduce any possible distraction and dedicate yourself to playing Shadow of the Colossus (and ignoring its technical shortcomings) I think you're in for a special treat.
I remember looking forward to playing it, but I had no clue as to what it is about or what to expect. I know that did I not intend to spend hours on it in the first go. Back then, it was quite a superb and unique experience. These days, the controls have not aged well. I also think it's a shame the original game can be made to look better in an emulator than in the re-released HD collection.
I would very much welcome a proper reprint with all the old goodies (or new ones) intact. But, alas, I guess that's just not very modern and it's definitely not how the majority of distributors roll these days.