It is safe to say that a player will likely spend a longer amount of time riding around on horseback in search of the Colossi than actually fighting them. Fortunately, this is actually a pretty fun experience. Even though there are no enemies to fight or puzzles to solve outside of the Colossus battles, the simple act of exploring the game world, seeking out one's targets, is very enjoyable in of itself. If anything, adding unnecessary complications would have detracted from this experience.
A great deal of the enjoyment I have derived from Shadow of the Colossus's exploration comes from the lack of guidance given to the player on how to proceed. Since the game's map is not marked with destination markers and is vague enough to be nearly useless, the payer is given only two clues on finding his next target: a short, cryptic description of the area by Dormi, and the Light of Guidence, which shines from the player's sword in the direction of the next Colossus. However, since the Light of Guidance needs to be actively checked by the player, only works when the hero is standing in strong sunlight, and only points in the relative direction of the next target and not the best path to reach it, the player often has to expend a lot of energy searching for his next destination. I have gotten lost numerous times while searching for a Colossus, and I often end up taking the long winding route instead of the short route. I have had to back-track, guess my way through winding canyon roads, climb up tall objects in a forest to find good sun-light, and so on numerous times in my search for the Colossi. Yet, I have often had a lot of fun doing so, since the act of trailblazing and pathfinding through a sprawling world is such a novel experience for me. Far too often, game developers make it far too obvious where the player's next destination is, or make it impossible to go too far off-track. This approach destroys the chance for the player to enjoy the search itself.
The lack of dangers and monsters in the game helps keep the focus of the experience on the journey itself. As it is, while riding around on Argo, I sometimes was reminded of stories of heroes riding great distances through forests and over mountains on a quest. If I had to get off my horse and kill goblins every few minutes, it would have broken that trance-like feeling. It would have also turned exploring the game world into a repetitive chore. Right now, Shadow of the Colossus is not a very repetitive game. Each Colossus provides a different challenge than the last, and each journey in search of a Colossus is different as well. Adding in minor enemies to populate the world would have required the player to fight the same meaningless battle over each time he passed through a certain area, which would have distracted from the newness of the journey itself. It would have dragged the travel portions of the game out too much as well.
Another thing I like about the exploration elements of Shadow of the Colossus is that it rewards the player for experimenting. During my search for the third Colossus, I noticed a lizard running across the canyon floor nearby. Seeing as how I had a bow, I decided to see if the game would let me hunt and kill the lizard, which it did. It even left a tail behind, which I could pick up. Later on, I discovered a lizard with an unusual white, glowing tail. When I killed that lizard and picked up the tail left behind, I discovered that my grip gauge had increased slightly. The game's manual hadn't even mentioned that there were power-ups in the game, so this was a pretty big discovery for me. After a bit more exploration and experimentation, I found fruit hanging from the branches of a tree that I could shoot down with a arrow and eat to increase my maximum health. These benefits are so slight, they are unlikely to turn the tide in an actual Colossus battle, but they do serve as a very effective reward for a player who takes the time to experiment and explore the game world. In particular, I like these rewards since they reward the player for doing what a person in that world itself would realistically do: hunt animals and gather edible fruit for food.
One final aspect of the exploration element of Shadow of the Colossus that I enjoy is the way Argo, the hero's horse, behaves. When the hero is riding Argo, the player doesn't directly control Argo's movement, he controls the way the hero commands Argo. So, getting Argo to turn the direction you want, get up to a full gallop, or stop can sometimes involve frustration and perseverance. On the other hand, Argo is also capable of following winding, narrow trails and such without a single button press from the player. In fact, it is sometimes easier to navigate by gently nudging Argo in the right direction, then letting him make the turn by himself. This make Argo seem like a real animal, instead of just a vehicle, which is a first in my experience.
It is very rare for me to find a game like Shadow of the Colossus where getting to your destination really is half the fun.