For many of the levels I've made, I've tried to come up with a (somewhat) original concept and a specific theme before I placed any tiles. I find it helps to have the music picked out early on so I don't have extra trouble finding a good music match for the level later on. If you start half a level and can't finish it, you can try stating a new level and get back to the other one some time in the future. You might even have to. I still have a bunch of unfinished levels in my Jazz2 folder, and some of my better work comes from resumed projects.

As for where to start the actual level-building, I can't tell you what's best for you, but I often start with the background to help me judge how many layers I'll need with x and y speeds at 1 (this issue also may depend on the tileset). If the background turns out to be really good, it's sort of inspiration to get the rest of the level finished. As to eye candy now or later, I probably don't stay consistent with my own choices. It's probably another thing that depends on the tileset. If you have to add a lot of eye candy, it may be easier to get it out of the way, but it'll make changing the layout around harder. I suggest trying a variety of methods and seeing what works best for you. You might not even use the same methods for each level.