The initial c may actually be the easiest part of cuius to explain. As mentioned in the comments, the old spelling of the word is quoius. It was regular for qu (/kw/ or /kʷ/, depending on your theory of Latin phonology) to simplify to c /k/ before the vowel /u/. See Why sequundus > secundus?
Similar sound changes have applied in English to wh- words, cognate (as a general class) to Latin qu- words. Wh is replaced with /h/ in both spelling and pronunciation in how, and in pronunciation (although not spelling) in who, whose, because of the following /u/ (currently present as the vowel in who, whose, historically present but later diphthongized in how).
The etymology of the rest of cuius
The source of the u in cuius is I think usually considered to be raising of short /o/ to short /u/. This kind of raising occurs in various distinct contexts in Latin, such as in non-initial closed syllables (second-declension -us -um < -os, -om), before /ŋ/ (unguen < Proto-Italic *ongʷən), and before /l/ followed by another consonant (vulpes < Proto-Italic *wolpis). I'm not sure however exactly what rule would cause raising in quoius.
I have seen an alternative account for the u that I don't think is currently accepted. A 1902 paper by Charles Exon, "The forms and scansion of the genitive and dative cases of is, hic, and qvi in Plautus"1, transcribes huius in Classical Latin with a long vowel in the first syllable ("hū-jus"), which is explained as deriving from "hoi-jus" by monophthongization of the original diphthong oi (pages 216, 218). (For the sound change, compare ūnus from Proto-Italic *oinos.) Exon applies the same explanation to quoius > cuius.
As far as I know, there is no direct evidence about the length of the vowel in cuius,2 but it is usually thought to have been short, with the heavy scansion of the first syllable in Latin caused by a geminate (doubled) /jj/: /kujjus/ (or equivalently, [kʊjjʊs]). The source of that geminate consonant and the final /s/ are other complicated/difficult parts of the etymology of this word.
The pronunciation of cui also has some complications (mostly unrelated to the initial consonant). Cui has a monosyllabic pronunciation, which many sources describe as ending in a diphthong [ui̯] (or equivalently, a vowel-semivowel sequence [uj]). However, I think I remember reading some paper where the author argued that the monosyllabic pronunciation was actually identical to that of qui. I don't know whether this issue has been definitively settled.
Hermathena, Vol. 12, No. 28 (1902), pp. 208-233, accessed through JSTOR
The high /u/ in Spanish cuyo, which would in most contexts correspond to Latin long /uː/, can be explained as an effect of vowel raising caused by the following palatal, as in huyo < fǔgio: "Notes on Romanic Speech-History," by
Edwin H. Tuttle, The Modern Language Review, Vol. 9, No. 4 (Oct., 1914), pp. 493-499.
Tuttle says the /u/ in cuius is from uŏ, but I don't understand what he means.