Like in most cities of ex-USSR, it's quite difficult to go without some knowledge of Russian. However, people under the age of 40 with higher education are capable of speaking some English. But don't expect English from hotel workers or maintenance staff in tourist places, policemen, salesmen and taxi drivers.
There are several planes every day from/to Moscow (from airp. Domodedovo). Also there is air connection with most largest Russian cities, and a few regular flights from abroad - Beijing, Tianjing, Harbin, major cities of nearest ex-USSR contries. KrasAir is a monopolist in the region, so you should check it's web-site www.krasair.ru for available directions.
Krasnoyarsk is located on the Trans-Siberian Railway, so every day tens of trains pass the Krasnoyarsk railway station. It takes about 12-14 hours to get to Krasnoyarsk from Novosibirsk and Irkutsk, minimum 60 hours from Moscow and Vladivostok.
Russian automobile roads and not very suitable for long-distance travels - no motels, no eateries, quality of roadbed does not allow to drive fast. However, there is a road connecting Vladivostok and Moscow, which passes through Krasnoyarsk.
Buses are available only from nearest region cities, and the neighbouring Khakassia region. They arrive to the City Avtovokzal located in the Northern part of the city called Vzletka. To date you're unlikely to obtain any information about avaiable directions and current time-table on-line. Usual price for trip up to 400 km is about 200-300 rubles (8-12USD).
During summer there are 1 and 2 weeks-long cruises to the Northern part of the Krasnoyarsk region to the Enisei mouth. Everyday connection is only with the Divnogorsk city located 40km West, near the Krasnoyarsk Hydroelectric Power Station.
There is a good network of public buses, which are indeed very cheap (6-10 rubles, or less than 50 US cents, per trip, and it does not depend on the distance; paid inside to the driver - in case of small buses called 'marshrootka' - or to the conductor). However, without a local consultant it's very difficult to plan a way, because no maps of routes on-line or on the bus stops are usually available. Numerous taxi carriers have appeared during the last years, phone booking is available (but unlikely your English will be understood) as well as hitching on the streets. In Russia it's a very common case when any driver who wants to earn some money stops near your risen hand, but in Krasnoyarsk you're strongly adviced to use only authorized carriers (it's a very safe city, but do not risk without necessity - many licensed drivers are available there), their cars must be marked with chess-board-like ornament on the top, and usually have some advertisement on the doors. Usually taxies are cheap as well (even if not using a meter) and honest, however seeing a foreigner some drivers can try to make you pay through the nose. Half-a-city drive should not be more than 150 rubles (6USD), if you suspect cheating - show your intent to complain to the driver's bosses.
Krasnoyarsk is a very old beautiful city, established by Russian Cossaks (military servants) in 1628. It's name consists of two words - Krasnyi (red, because of clay reddish soil) and Yar (steep bank). Views of Enisei river and nearest Sayan mountains covered by taiga forest are very pictorial.
Forest Reserve Stolby (Заповедник Столбы, or Pillars in English ) is a very famous place among alpinists all over the world. Stolby covers an area of 470 km² (181 mile²) with numerous giant granite rocks formations up to 100 meters high, many of very extraordinary shapes - Ded (Grandfather or Дед), Babka (Grandmother or Бабка), Slon (Elephant or Слон), Peria (Feathers or Перья). The last one is the most dangerous rock, which has alsready taken tens of climbers' lives. Stolby is a major rock climbing location, many local climbers intentionally do not use any belaying equipment and call their extreme sport "stolbizm", which is known around the world as solo climbing. You should take a bus to the 'Bazaikha' or 'Turbaza' (currently it's number is 50a), and walk 7 km through the forest to the First Pillar (Pervyi Stolb or Первый Столб). Most of the distance goes upwards, the last 400m are extremely steep and because of that are called Pykhtun (Panter or Пыхтун). There is also a cable car way to the Reserve. Check the web-site for more details: http://www.stolby.ru/eng/. Divnogorsk city (Дивногорск, means "Wonderful Mountains") - 40 km West, half an hour by river (only in summer) or by train from Main Railway Station (железнодорожный вокзал). The views to the river and mountains are excellent. Karaulnaya Gora (Караульная гора) hill with the Paraskeva Pyatnitsa Chapel is a symbol of the city, it is depicted on the 10 rubles note. The surrounding areas are local Harlem (populated with criminals and drug-trafficers), so you should not try to walk there.