To try to answer some of your questions...
1) The screen is typically drawn as tiles. You can simply have a data structure with the type of tile at each location.
2) The simplest form is a tile is either movable or not. The next step is probably supporting a square tile with a triangle shape (from corner to corner).
3) Objects outside the viewport are not drawn. When the character moves, the map and any objects are redraw to show the new location.
On very large maps some tricks can be done, like not running the AI for an enemy that is very far away. When the player gets close enough, but with the enemy still not on screen, then you would run the AI.
You might look at Slick and TilED.
Demo of tilemap with Slick:
http://slick.cokeandcode.com/demos/tilemaptest.jnlpMore interesting, scrollable tilemap:
http://slick.cokeandcode.com/demos/scroller.jnlpTilED editor:
http://mapeditor.org/tiled.jnlpTilED homepage:
http://www.mapeditor.org