I focus a LOT on RP so my take will be different than minmaxing. I can see starting as a Fighter, one that is very devote and becomes a Paladin. IF I was going to multiclass these two I would take that option. First two levels as a fighter and then go Paladin.