Both types of battles involve playing cards from your hand into a line of 3-5 slots in an order that forms pairs, straights, and flushes for bonus points added to the cards' base values. The total needs to exceed a goal value for you to either get the full skill increase from the job being done, or get the successful branch of the story event in progress. A tutorial (click the question mark at the top-right of the challenge screen) explains scoring rules and how to play.
Job challenge difficulty is determined by age, whereas story battles may vary depending on how easy or impossible a task is being performed. Challenges in some explore regions will be much harder than those in others.