Should I detect the device or the page first?

Disregarding for a moment the comments telling you to avoid user agents (because they are error prone and will probably fail on some devices – as you can see from the constant stream of bug fixes on the plugin), the answer to your narrower question is: it doesn’t matter.

If A and B are independent of eachother, as in this case, there is a logical equivalence between if A then if B do C and if B then if A do C and if (A and B) do C.

It could be different if a lot of processing time was involved in checking the user agent and there would be a page condition where you didn’t need a different version for mobile. But as you state it, you always have to check both user agent and page type before you start doing something. Then the order doesn’t matter.