if you can go "up" the wall and out the top plate and then back over the ceiling to the other wall, that would make sense to go in-wall. If you need to run horizontal thru the walls, that means a lot of cut-outs and repairs to get the holes drilled in the studs for the wiring to pass thru. A possible "exterior" solution is the plastic cable ducts that mount/glue to the wall base trim moulding - or replace the moulding. It has snap on covers to contain and conceal the wiring.
As far as what to run, please try to really think through all the various audio/video sources you have now and will have in the future.
suggestions:
2 HDMI cables (could need both until you get a audio/video HDMI switching a/v receiver, probably only need one after that)
1 component set (3 wire) of cables
2 TosLink optical cables (one from the TV ATSC tuner to the receiver for OTA audio, one spare)
1 pair red-white stereo audio cables (what the hell, you never know)
1 75 ohm RG6 coax antenna cable (you might want to receive over-the-air TV ? )
A lot will depend on whether you want to purchase a up-converting a/v receiver which switches both audio and video to the HDMI cable running from the a/v receiver "out" to the TV "in". The only problem with the receiver doing the switching is that it must always be "on" while watching the TV. But, that is its function as the centeral switch for all the inputs to a single output.
order your long cables from
www.monoprice.com I have made several installs, both at work and for family, using their cables and have had excellent results. The prices are outstanding !!!