Using VS you'd be teaching VisualBasic.Net which is much different than the basic of old.
VB.net is Object Oriented. If you want to teach a .net language teach C#. The syntax of VB gets in it's own way and makes things much more complex/verbose then necessary.
.Net in general is geared toward windows application development which means it is geared towards forms. It is actually extremely easy to pick up WinForms in C#/VB but that means that if you are learning it as your first language you are learning more about event driven logic rather than the procedural logic it sounds like you are expecting.
Get one of the IDEs from the download page, I recommend fbIDE.
The fitness function may be simply, how much dmg the player received while in the area
The second level would be 9 more 3x3 areas where each area is composed the same way a new enemy unit was composed.
Of course, in this instance I wouldn't be surprised if the player eventually ended up in 9 3x3 areas made entirly of lava... Obviously the most difficult terrain, but also not fun because it is impossible to survive, then again if the player ended up with Lava protection or something, the board would start to evolve toward... spikes or slow (as long as the lava protection was effective enough).
I was thinking of the same sort of thing for enemy AI for a top down shooter.
There really isn't enough information provided to be able to recommend a solution, but what I was thinking was something along the lines of letting bots stats determine their speed/accuracy/toughness/damage etc, with a caveat that the combined stats couldn't breach a maximium in addition movement patterns and tracking strategies would be part of the DNA. Then setting up some kind of metrics to measure how well they did against the player. How long did the bot live, how many times did it score a hit, how much damage did it cause etc. Then use those metrics to define which AI's should have the higher fitness scores.
I was hoping that this would make it such that players that are very accurate will find themselves fighting quick nimble erratic bots while those that didn't dodge as much/well would find them selves against tougher slower more powerful ai's. I never got to the point to implement any of this though, so I don't know how well it would have panned out.