In that E3 video the randoms don't look random! I could have sworn I had read that it had random battles. Oh man am I ever relieved. Like so so sooooo incredibly releived!! Seriusly cant wait for this
They said in the interview with IGN I think that you can see the enemies, and avoid them if you wish.
However, in almost all games where you can see the enemy ... I find most fights still impossible to avoid so I don't really get the appeal. The only plus I've seen is that you can wonder around a bit more in areas you've cleared without more fights.