It has me a little concerned that your doctor suggested that you supplement your daughter's diet with solids rather than pumped breastmilk or even formula. I get that your wife is returning to work and won't be able to breastfeed as she can at home, but, at this age, all of your daughter's nutritional requirements should be met with either formula or breastmilk, and, solids, if introduced at this time are purely to allow her to practice the process of eating and become accustomed to new textures. They will probably not provide enough nutritional value to her to replace breastmilk or formula. While it's not unheard of to start a baby on solids at 4 months (my son started on solids at 4 months and was quite happy with them), 4 months can still be a little young for some children. My daughter wanted absolutely nothing to do with solids until she was 6 months old. Until a child is somewhere between 4-6 months old, he/she still has the tongue thrust or extrusion reflex. Just because she's pushing food out of her mouth doesn't necessarily mean she doesn't like it--just that she hasn't lost this particular reflex yet. What this means for you is that most of the food you place into her mouth is going to be forced out and very little, if any, is going to be swallowed. It is unlikely that at 4 months that she will open her mouth voluntarily for food on a spoon.
For a long time, doctors recommended starting babies on iron-fortified cereals like rice cereal mixed with water, formula, or breastmilk. It could be warmed to room temperature if you desired, but it was not necessary. Doctors are moving away from that and simply suggest that you introduce new foods VERY slowly. If you choose to introduce applesauce, feed your daughter applesauce everyday for 3-4 days (some doctors recommend as long as a week), watching to make sure she doesn't show any signs of an allergic reaction to the food. If no reaction occurs during those 3-4 days then you can move on to introducing another new food like sweet potatoes or peas. Otherwise, the order in which you introduce foods is entirely up to you. This site has a very nice guide on introducing foods to babies, including the clues to look for that indicate that your baby is ready for solid foods (sits well in a highchair, shows interest in food, can close mouth around spoon, etc.).
It's very easy when babies are little to become frustrated with them when it comes to solid food. One day, they're all about eating whatever you put on that spoon, and the next day they want nothing to do with it. Relax and go with the flow. Eating, at her age, is not really for nutrition so much as it's to experience different textures and flavors.