What is the nuance between 手数 and 手間?

I've found the dictionary definitions of 手数 and 手間, both that are translated to "time, labor":

手数

１ それをするのに要する動作・作業などの数。てかず。「―のかかる料理」

２ 他人のためにことさらにかける手間。てかず。「お―でもよろしく」「お―をかけて恐縮です」

VS

手間

１ そのことをするのに費やされる時間や労力。「―を省く」「―がかかる」

...

３ 手間賃を取ってする仕事。手間仕事。また、その仕事をする人。「―を雇う」

What I don't understand are the nuances. I.e., when can/should one be used and not the other, or when can both be used.

Answer

There is a hint in the differences by looking at the different characters used: 数 vs 間.

数 indicates that numbers are involved, as seen in the definition of 手数 → 動作・作業の数. In other words, the number of steps or amount of work necessary is the focus.

間 indicates that time is involved, as seen in the definition of 手間 → 費やされる時間や労力. In other words, the amount of time and the amount of effort is the focus.

So, let's look at some examples:

手間がかかる料理

手数がかかる料理

I think both of the above phrases could be used, but the focus is different. The first implies a dish which takes a lot of time and effort to make, while the second one implies a dish which requires a lot steps to make.

XXのネットサービスを利用すれば、お店まで行く手間が省ける (If you use XX internet service, you don't have to go all the way to the store)

In the above sentence, since we are talking about effort, I think 手間 is more suited than 手数 because we are not talking about something that involves multiple steps, etc. we are talking about the effort of going to the store.

There is another different between the two:

お手数おかけします

You might see the above often as a fixed expression. However, we cannot use 手間 here. Why? Because 手数をかける is always directed toward somebody else and implies somebody else will do something for you (as noted in your second definition), whereas 手間をかける will imply something that you do yourself, such as 手間をかけて作ったケーキ (a cake that you put time and effort into to make).

Also, 手間 often has a strong emphasis on time, like in the following sentence:

XXのインストールに手間取った