Here is a compiled list of the hidden and some of the more cryptic achievements, from both personal experience, this list, and research (Googling, asking other ppl, etc). Let me know if any corrections are needed.

Some achievements might not pop up, so check for your profile to see if you obtained it.

Only the Booster 2.0 and the Iron Bond (by rescuing Curly) are required for the Best Ending (which you get after beating Ballos in the Sanctuary/Sacred Ground/Hell).

The 290 Counter (formerly the Nikumaru counter) is for the speedrun/time challenges (to unlock new tracks and characters on the title screen). The Whimsical Star helps a lot with the archers in B3 of the Sanctuary/Sacred Ground/Hell. Both of them are optional.

The Spur and Booster 2.0 is useful against Ballos' first 2 (and a half) forms.

Date related

"Happy Birthday Pixel" can be obtained by playing the game on April 29 or just set your computer date to April 29.

"Merry Holiday Happy Euphemism" is obtainable by playing the game during December 24 or 25th OR by setting your computer date to December 24th or 25th. You'll know you got it if all the sprites (and levels) are holiday themed - there's no popup for this achievement for some reason. See video.

Item related

"Ladies Man" can be obtained by sleeping with Chaco in Bushlands. All you really have to do is talk to her (check the fire at her house for the first time), and then sleep in the bed. You'll pick up the item when you wake up.

"Return the Favor" is somewhat tricky -- you have to unlock the secret dungeon by completing a series of tasks from Labyrinth onwards, then just get to a certain point in the dungeon (it's early on, in the first room, when you attach Curly).

"A Gift From Santa" is obtained by getting the Fireball, which is given by Santa of Grasstown as thanks for finding his key.

"A Fine Blade" is obtained by getting the Blade which you get after finishing the Sand Zone.

"Super, thanks for asking!" is obtained by getting the Super Missile Launcher, which is found in the Boulder Chamber after defeating Balrog.

"Arm Bar" is obtained by getting the Arms Barrier in the Labyrinth, behind a door in the high up passage above the physician.

"Turbocharged!" is obtained by getting the Turbocharger obtained from Chaba in the Labyrinth shop.

"Panty Raider" is obtained by finding Curly's panties. If you go to Curly's room there's a secret passage which leads you behind the wall and to the far right of the room. There you can find her panties.

"Tow Me A Rope" is obtained by getting the Tow Rope. Found in the Core's room (BEFORE the battle). The Tow Rope only appears if you did NOT get the Booster 0.8.

"Little Man" is obtained by finding Mr. Little. He is in the Mimiga Village Graveyard (he's green and extremely tiny, keep your eyes out).

"Home, Sweet Home" is obtained by taking Mr. Little home and talking to his wife (again). His home can be found below the Outer Wall.

"Ducking Awesome" is obtained by getting the Nemesis. After taking Mr. Little home, trade him your blade for the Nemesis.

"Freakin' Laser Beamz" is obtained by getting the Spur. Trade the Polar Star back to the Hermit Gunsmith (Use the Booster 2.0 to reach to the first cave and talk to him). If you collected the Machine Gun or the Snake, you won't get it in that game. If you got the Booster 0.8, instead of the 2.0, it becomes much harder to reach the cave to get the spur, but it can be done.

"Cold Hearted Snake" is obtained by getting the Snake. The shopkeeper in the Labyrinth Shop will combine your Polar Star and Fireball to create the Snake. If you collected the Machine Gun, you won't get the Snake in that game.

"I've Got Your Back" is obtained by getting the Iron Bond. This is obtained by returning Curly's memories by stuffing the mushroom in her mouth and then talking to her again.

"Count to 290" is obtained by getting the 290 Counter. If you have the Booster 2.0 and also saved Curly, you can get the 290 Counter from the chest in the clock room near the beginning of the Outer Wall. Otherwise, a mysterious force keeps the chest closed.

"Supa Star!" is obtained by getting the Whimsical Star. You get it from Chaba in the Labyrinth shop after you go back after obtaining the Spur.

Boss/Battle/Player related

(Some of the Boss related achievements might not work in Curly mode)

"Here's Johnny!" is obtained by getting the Alien Medal, which you get by defeating Ironhead without taking damage.

"Toroko Wins" is obtained by losing to Toroko w/o hurting her.

"Doggy Style" is obtained by beating Omega with one of Jenka's puppies.

"Only If You're Greedy..." is obtained by defeating the Twin Dragons.

"Swollen Mech" is obtained by defeating Heavy Press.

"Hate Made Flesh" is obtained by defeating Ballos.

"Cave Story Clone" is obtained by defeating G-Clone

Level/Mode related

"To Hell and Back" is obtained by completing the Blood Stained Sanctuary/Sacred Ground/Hell

"Who's the Boss?" is obtained by completing Boss Attack mode.

Challenge related

"Wind Fortress" Complete the Wind Fortress level in...

• Rank C: < 7 minutes
• Rank B: < 6 minutes
• Rank A: < 5 minutes
• Rank S: < 4 minutes (Although that is what it says in the achievement, you won't get it unless you complete it in < 2 minutes)

"Sanctuary" Complete the secret/optional Blood Stained Sanctuary level in...

• Rank C: < 6 minutes
• Rank B: < 5 minutes
• Rank A: < 4 minutes
• Rank S: < 3 minutes

"Boss Attack" Complete the Boss Attack mode in...

• Rank C: < 15 minutes
• Rank B: < 12 minutes
• Rank A: < 10 minutes
• Rank S: < 8 minutes

Ending related

(Some of them might be bugged for some people)

"Mimiga Hero" is obtained by keeping the Mimiga Mask on (not getting the Booster back[...the final boss gauntlet xP]) and beating the game with it. I think it can be done on Easy.

"Coward" is obtained by flying away on the dragon with Kazuma in the Bad ending. (Blue Raja got it, but I was unable to :/)

"Unstoppable" is obtained by obtaining no life capsules and getting the Best ending.

"Untouchable" is obtained by obtaining no life capsules and getting the Good ending.

"Curse Broken" is obtained by getting the Best Ending. Clear the Blood Stained Sanctuary/Hell and beat Ballos.

"Shtuff Happens" is obtained by getting the Normal ending.

You are mostly right. The levels where the gifts are located are Academy Hallways, Crystal Caves, and Dragon Graveyard. This video shows their exact locations: