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.
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.
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.
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.