East Kalimantan  (Kaltim) is the easternmost and the northernmost of Kalimantan. Best known for the beautiful beaches along its east coast, it stretches from the Celebes Sea near Malaysia into the Makassar Strait.
Mancong and Tanjung Issui Village; These two village inhabited by Dayak Banuaq living on a long-house. Most visitor take a house boat on Mahakam River beginning from Loajanan the area just before Samarinda City from Balikpapan. Tanjung issui has a very well preserved long house, remodeled on the inside as a museum and hotel in the back with great rooms and a lovely view. Down the road from Tanjung Issui, Mancong's two story long house is inhabited by families and there are regular dance performances. it is very well decorated outside with many traditional banuaq style wood scupltures.
Further up Mahakam River, Tering Village where Dayak Tunjung and Kenyah with long ear woman are worth to visit. Next to Tering is Melak Village, the location of Black Orchid garden, it is called Gersik Luai it is a good 20 or 30 minute drive deep into the wilderness. Black Orchid season is late spring through autumn but you can see other species throughout the year.
Two other longhouses worth visiting in this region are in Aheng (up the road from Melak) and Bigung (between Tering and Kutai Barat) Aheng has many people living in the antique longhouse decorated with many artefacts and handicrafts. The ages of the inhabitants range from babies to old grandfathers. Here you can buy your very own, brand new Mandao. (Dayak Machete)
The longhouse in Bigung is almost finished, being brand new it lacks in antique charm however it does feature some very special distinctly Tunjung style sculptures which are a rarity. More famously, the Bigung longhouse is known by locals as the Dayak Casino where they play traditional Dayak games round the clock in their makeshift Casino under a several huge tarps. Real cash and real Dayaks of all ages playing thousand year old games, which the local english teacher will try to explain to you. Cockfighting every other afternoon weather permitting. Delicious food is available.
The Regional capital city Kutai Barat features 6 huge (non residential) longhouses funded by the government. They are meant to be an eternal showcase of the best of Dayak architecture, sculpture, design and painting. The 6 are decorated in the 6 artistic styles of 6 local Dayak tribes including Tunjung, Benuaq, Kenyah and Bahau. Although they are massive, impressive, shiny and spotless, they lack greatly in the authenticity that can only be found in smaller villages. There is a big Dayak dance festival with performances from the 6 major tribes held every 2 years at Christmas time, the festival includes a buffalo sacrifice.
East Kalimantan is the center of Indonesia's timber, oil and gas industries. As you might guess, the stripped coastal areas are not a pretty sight, but the province's more interesting sights lie far upriver in areas untouched by the voracious logging machines.
East Kalimantan is where the Banjar social influence ends and the Dayak society begins. As you go from South to North, or east to west, you see Islam becoming a minority and the banjars becoming smaller ethnic pockets. Dayak civilization is divided into tribes which hold their domains across the region. In all but the furthest reaches of the rivers, the Dayak ethnie has modernised and urbanized. The overwhelming majority of Dayak people live in villages, watch TV and have cell phones. They preserve their culture as best they can and the chidlren are bilingual (Dayak dialect and Bahasa they learn in school) many cultural mediums have survived and their tradition is even funded by local government. There are no Dayak school or Sunday school programmes for the children to learn more about Dayak history or mythology. So their understanding of their culture is limited to what their parents and friends can recount.
Art forms like sculpture, painting and song are threatened by the modern age, however dancing, language, games, and architecture are well cherished by Dayaks and visitors alike.
You can also access Kalimantan Timur from Tawau in Malaysia. From Tawau there is a boat to Tarakan. From there another one to Nunukan in Berau district. You need a visa to enter Indonesia on that port (Visa on arrival is not available) but there is an consulate in Tawau which seems to do visas quite quick.
Visiting Mahakam River hinterland and orangutan or exploring kutai national park is the best option.
There is quite good diving on on the east coast.