R - 166 characters

library("plyr");s=function(a){l=table(strsplit(a,s="")[[1]]);l=ldply(l[order(-l,names(l))],function(n)data.frame(seq_len(n)/n));paste(l[order(l[[2]]),1],collapse="")}

ungolfed version

library("plyr")
s <- function(a) {
    tbl <- table(strsplit(a, split = "")[[1]])
    tbl <- tbl[order(-tbl, names(tbl))]
    tbl <- ldply(tbl, function(n) {data.frame(seq_len(n)/n)})
    paste(tbl[order(tbl[[2]]),1], collapse = "")
}

Explanation:

• Split into individual characters
• Tabulate number of each character
• Sort table into most frequent and then by lexical order
• Index positions for selection at 1/n, 2/n, 3/n, ... n-1/n, 1 where n is the number of candies
• Sort candy names by index (order is stable in sorting, so will maintain the most frequent/lexical naming order when a tie in the index, particularly important with the last candies)
• Concatenate the candy names together to make the output string

R - 166 characters

library("plyr");s=function(a){l=table(strsplit(a,s="")[[1]]);l=ldply(l[order(-l,names(l))],function(n)data.frame(seq_len(n)/n));paste(l[order(l[[2]]),1],collapse="")}

ungolfed version

library("plyr")
s <- function(a) {
    tbl <- table(strsplit(a, split = "")[[1]])
    tbl <- tbl[order(-tbl, names(tbl))]
    tbl <- ldply(tbl, function(n) {data.frame(seq_len(n)/n)})
    paste(tbl[order(tbl[[2]]),1], collapse = "")
}

Explanation:

• Split into individual characters
• Tabulate number of each character
• Sort table into most frequent and then by lexical order
• Index positions for selection at 1/n, 2/n, 3/n, ... n-1/n, 1 where n is the number of candies
• Sort candy names by index (order is stable in sorting, so will maintain the most frequent/lexical naming order when a tie in the index, particularly important with the last candies)
• Concatenate the candy names together to make the output string

The matrix nature of the problem made me think R might have a shot at this, but the best literal interpretation of the algorithm I could do was 211 characters:

l=function(a){l=table(strsplit(a,s="")[[1]]);l=l[order(-l,names(l))];o=Reduce(`*`,l);m=matrix("",nc=o,nr=length(l));for(r in seq_along(l)){x=l[r];for(c in seq_len(x)*o/x){m[r,c]<-names(x)}};paste(m,collapse="")}

ungolfed:

l <- function(a) {
    tbl <- table(strsplit(a, split = "")[[1]])
    tbl <- tbl[order(-tbl, names(tbl))]
    o <- Reduce(`*`, tbl)
    m <- matrix("", ncol = o, nrow = length(tbl))
    for (r in seq_along(tbl)) {
        for (c in seq_len(tbl[r])*o/tbl[r]) {
            m[r,c] <- names(tbl[r])
        }
    }
    paste(m, collapse="")
}