Ok, I've just bought my first Android smartphone after 10 years with a Nokia 36XX paleophone.
It seems like a new world XD

Do you have any advice about settings or about apps to use\avoid?
(for example, I've read that Greenify isn't good anymore, or that Whatsapp is crap)

Also, I'm usually quite paranoid with privacy, but.. it basically seems impossible with Android+Google O_o

If you drive, I recommend Waze.
If you're vegan or vegetarian, I recommend HappyCow.

First of all, you should think what you want to do while on your phone. If all you want to do is to send/receive calls/messages, you're fine as it is. If you're also interested in listening to the radio and to music in general, if you have a Samsung phone (as I do) the default apps offered by Samsung should work fine enough. Otherwise, I'd advise against Google Play Music (it seems to be one of those apps that want the internet for everything) and for music I'd suggest -it's an old app sure but will do if all you want is to hear music with no strings attached. In case you want to play games for when you're in a waiting room or something, I'd suggest [url=https://play.google.com/store/apps/details?id=com.magmamobile.game.Solitaire]Solitaire (I have this one on my phone, but there are others too), Flat Frenzy and Fur Guardians.
For browsing the internet, nothing beats imo Opera Mini -it's lightweight and shows gog's frontpage and forums reasonably well, although I haven't tried to login from my phone.
In case you wish to read documents and pdfs on your phone WPS Office shoudl do the trick.
Anyways, I personally tried to avoid apps with lots of permissions -the 2 latter games I mentioned don't request any for example -do check which permissions the apps ask, since you also appreciate your privacy!- and do not install Facebook/Twitter on your phone if you don't absolutely need them.
Anyways, sorry for the verbosity, but that's the basic stuff. If you want more info, just ask.

I always install Shattered Pixel Dungeon on my phones, it's a great time killer and it works well on a small screen

F-Droid if you'd prefer to use open source apps. It's complementary to Play, so no convenience lost.

Signal (TextSecure up until a few days ago) for (end-to-end encrypted) messaging and calls.

Root it and/or install a custom ROM if you don't care about the warranty. Rooting it enables you to control app permissions, which is a feature inexplicably missing from Android versions prior to 6. A custom ROM will enable you to get rid of the Google crap, but you might find that somewhat inconvenient.

I like CoolReader for books (EPUB) and Lightning (mainly for built-in ad-blocker, since not using one is an exercise in masochism) for browsing (Firefox is an option, but a buggy, unstable, and feature-deprived option, though YMMV).

If you frequently order stuff online and get tracking numbers, I would recommend ParcelTrack so you can easily see when your new thing will arrive.

If you enjoy Doctor Who, or just want something to waste a few minutes while waiting for the bus, get Doctor Who: Legacy, it's basically a match-3 with a few twists.

OMG, I am not the only guy who got his first smartphone this month!

Am I the only one that still doesn't have a smart phone, or for that matter, a cell period?

That actually makes three of us.

Some of Humble Mobile Bundle
and Humble PC and Android Bundle are good too It could have been 4 of us but GOG sale kicked in... :/

Stuff I'm using on a regular basis:

Inkpad, a basic notepad. Can sync with Google-take-over-your-life-whatever stuff. Sync is optional.

Zedusa Lite, to resize photos. This older MotoX takes one size of photo - enormous - so I resize everything before texting / mailing.

I also snagged some of the old HTC Sense UI stuff, since I came to like having that with an older phone of mine. Various widgets that provide handy at-a-glance info.

1Weather, though there may be other, better weather apps out there.

Dropbox, because Dropbox. And it's not Google

Skype, since a couple customers prefer using that over text.

Some flashlight app. This is quite handy.

Basically a biz phone for me, so much of the pre-installed stuff works fine. Am trying to pare down the Google crap, though. Unfortunately, without rooting it the best I can do is disable various Google apps instead of uninstalling that stuff. Dear Google - I don't need a Hindi keyboard, so why can't I uninstall it entirely?

Dunno what other people will say about it, but I generally stick with setting it on 3G, since 4G seems to suck battery pretty heavily. For me, 3G will stream most stuff just fine with only a little bit of buffering - certainly handles audio streaming no problem.

I couldn't handle anyone having cell periods every month.

Osmand for offline maps;
GPS Test, GPS Status & Toolbox - for GPS diagnostics (to see how much GPS satellites are out there, how much are used by your phone, to update A-GPS data for future offline-only use, etc; compass included!);
ColorNote - good app for taking notes, making todo lists;
In addition to already mentioned CoolReader, i can mention FBReader (it can also read pdf and djvu files if you install FBReader plugins from Google Play, so there is no need for separate app for that);
I also use Bluetooth File Transfer program, because android's stock version is not working in my case. Very useful bluetooth software.

I had a feeling someone was going to jump on my questionable choice of wording. XD

Living in a house with 3 females and a female dog, I always cover those bases.