Dancing has two factors that impact the difficulty -- the looks of the governor's daughter and the overall game difficulty. The easiest dances are thus available on Apprentice when dancing with a plain girl, but the easiest dances typically have fewer steps.
I'm 95% certain this can't be achieved on Apprentice difficulty, but it can be achieved on at least Journeyman difficulty. I was able to earn this on Journeyman dancing with a beautiful girl.
-----------------Tips-----------------
*Not all songs are created equal. You may be better with one dance than another -- as long as the dance has at least 150 steps, work towards your strengths.
*At this level, you will start getting quick double-taps -- you may also have steps that quickly move around the screen. Practicing the same song multiple times will allow you to memorize the pattern which is crucial when your finger blocks some of the screen.
*You must COUNT the available steps in a dance before you bother practicing it. There is nothing more frustrating than getting 100% of the steps perfect for a dance that ends at 148X. Even when I was playing on Journeyman and dancing with a beautiful girl, two of the dances had less than 150 steps. Some of the dances have quick steps that are difficult to count -- I used a scratch pad and made tick marks while missing every step.
*There are at least 5 different dances. At this level, the dance that starts with 4 steps (circles) moving left-to-right across the bottom of the screen does not have enough steps to earn the achievement. The songs may start to sound similar, and some of the dances start in similar ways, so it helps to really hone in on something that makes your chosen dance stick out, either musically or in the order the circles appear.
*You can quit to the main menu at the beginning, middle, or end of a dance -- just pull up the menu in the lower left hand corner, hit the arrow in the lower left hand corner, and select the key at the bottom right of the screen (this is the same place you'd save, load, etc.) When you quit to the main menu you can reload your autosave and go back into the city to start up another dance.
Note: The game will initiate an autosave just before you enter a city every time.
*You may experience dances ending prematurely. If you notice you skipped a cutscene when you were trying to initiate a dance step, the dance didn't play to the full length. I advise quitting the game and reloading. I noticed this started to happen when I had loaded several autosaves in a row while trying to get the right dance to pop up.
*The achievement pops immediately -- you don't need to wait until the dance is finished.
*You may want to turn on airplane mode. Text messages (SMS) and emails can lag the phone and will make it very difficult to get perfect steps.
*I earned this without special items, so I know it can be accomplished without them -- I plan on doing some additional testing with items later. However, Uranium Deposit says that the computer version's special items for dancing merely reduces stumbles - this should not have any bearing on your ability to earn the achievement.
*The video added is just the music for the song that I used to achieve Musician. It was not actually my first choice as I found another song to be easier, but this one was similar and I practiced it along with the other. There are some tricky spots, like the quick double-taps three times in a row, but for the most part the music and the steps go hand-in-hand (steps are in sync with the downbeats, mostly). There is a tricky part where the rhythm changes slightly, but with a little practice it becomes simple.