The reason why Ice Pokémon are found so late in the game is probably because of the "wilderness factor" of Ice. You only find them in the deepest caves, or on the highest, snowblown mountains. Very rugged, hard-to-reach terrain which wouldn't serve early-game, when you're walking through meadows, forests and even gardens. The games are meant to start in your back yard and take you through increasing levels of wilderness. Game Freak seems to think snow and ice only forms in the most extreme locations there is, hence why Ice Pokémon are usually relegated to late-game wilderness.
We talked about the lateness of the Ice type on IRC recently, and found out that Cold Storage with Vanilite is the earliest available Ice type in the games - just before the 5th gym. A possible contender is RBY Shellder, found in Vermilion Harbour (available via Good Rod, which may be acquired before beating Erika) which may then be evolved into Cloyster with a Water Stone from Celadon Dept. Store. GSC also lets you find a Lapras on Fridays, by backtracking to Union Cave after getting Surf. This means you can have an Ice Pokémon before you progress beyond the 4th Gym city, but it's not as readily available as Vanilite is.
Considering that XY even gives you Dragon types - traditionally the most overpowered type - before even the second gym, it just makes an example of how screwed over and poorly executed the Ice type is in the core series games.
EDIT: I realized after writing this that Amaura can be revived from the Sail Fossil even before the second gym in XY. Still, it's a very optional Pokémon, and you won't see it in wild encounters. I still hold onto Vanilite being the earliest, wild Ice Pokémon.