You’re probably not doing anything “wrong” as such. The problem described is common and depends on the charcoal used. Some charcoal (even if labeled “quick light” etc) is nearly impossible to get going. Holding it with tongs over an open flame (and blowing on the coal periodically) normally works, and it may or may not spark. The trick there is to make sure a good portion of the goal is glowing red before imposing incense. This can take some time, kind of like lighting a charcoal grill without the help of lighter fluid. I’ve had this problem even in church when the pastor made a big mistake and bought the wrong coals. We ended up throwing them out.
Some “ethnic” stores (Greek, Middle Eastern, Indian, etc) have foil-wrapped rolls of charcoal (each about the size of a quarter). These normally have a raised lip on the circumference creating a “well” in the middle to hold the incense. They’re very inexpensive and if you find the right brand, they light in a jiffy, (sparks and sizzle and all) just with a match (stick matches are still best). These can also be found in Orthodox church-supply stores. You could also get the larger “5-point” coals (slightly larger than a US dollar coin) that are often used in church. Those can be broken (in thirds, or in half then in half again – but always gently so they do not crumble too much and lose the “starter”), and they usually light without much problem.
Any incense is fine. It’s strictly a matter of taste. To get the “churchy” effect, though, I would recommend a church blend, available at any church supply house and even on-line. Just do a google and see what comes back.