I think it's worth working out what the common textures are and then storing them ready for later instead of loading each one before display, is that what alphablackwolf is saying? You have a 19x25 grid so if you've only got grass and dirt, maybe you only need to load two textures each time instead of 475.

Regarding the map loading, if you look at the Hexwar project I posted somewhere on this forum, I managed to get the map to load from a database that also stores the texture image file locations and so on. Feel free to use it, there's a .bak file in there somewhere for SQL Server Express. This surely is one of the easiest ways to store the board and it leaves you free to think about making an editor later on because you know the format will be something sensible.

Be mindful of what you put into Update and Draw - do as little as you can in there, and as much as you can outside.

Any one-off, IO, or instantiation of objects, as a strong rule of thumb, should not be inside those loops.

You can find a decent map-editor in Tiled, which can be used together with Gravelyn's TiledLib for XNA.