New smartphone user: Free/open software Unixy-apps/tools for Android phones?

I finally decided to move to an Android smart phone (aka mobile computer tracking and monitoring device designed to display ads).

I'm shocked at the sewer this device is -- a proprietary world of garbage, spam and ads.

What I'm looking for is computer tools/utilities, programs and apps that a typical Linux power user would use. Everything from a Dvorak keyboard layout, to cool toys, games, ssh/scp/ftp/mail clients, to network tools to ... you name it.

The gotcha?

All app recommendations must be ad-free with no in-app purchases and sane permissions (sorry, I want to give as few permissions as possible, a philosophy that seems to be foreign to the Android environment).

And also: Does anyone know if it's possible to replace the "