Problems for which a small change in the statement causes a big change in time complexity
Given a graph, does it have a cycle of length $3$ ($4$)? Four-cycles there is an easy algorithm that requires $O(n^2)$ time. The best known algorithm for triangle detection is related to matrix multiplication and has complexity $O(n^\omega)$ where $\omega$ is the matrix multiplication exponent. It is an open problem to determine whether $\omega=2$.
Given a graph, decide if its vertices can be colored with 2 (3) colors. Two colors: it is equivalent to testing the graph for bipartiteness, Three colors: NP-Complete.
Given a graph, decide if its edges be colored with 2 (3) colors.
Two colors: trivial (color an first edge arbitrarily, follow all implied edges, repeat). Three colors: NP-Complete.
Given a system of Diophantine equations, does it a admit a (non-negative) solution? Solvable in polynomial time if variables can be negative, NP-Complete otherwise.
Given a graph and two vertices $s$ and $t$, what is the length of the shortest (longest) path between $s$ and $t$? Shortest path: essentially a BFS. Longest path: NP-hard.
A lot of graph problems that are hard in general, are easy on trees (vertex cover, independent set, dominating set, ...). See Kleinberg &amp; Tardos, perfect graphs, and notice that a minimum dominating set on a tree can be found by greedily selecting a parent $v$ of a leaf, deleting $v$ and its neighbors, and repeating.
Given a directed graph, can you partition its edges into paths of length 2 (1)? For paths of length 1 the problem is trivial. For length 2 there it is a generalization of 3-dimensional-matching.
Given a set of numbers, can it be partitioned into groups of 2 (3) elements so that all groups have the same sum? For groups of two elements it is trivial (the match of an element is completely determined by the element itself). For groups of $3$ it is the 3-partition problem.
Given a NFA, does it accept (reject) at least one word? Accept: this boils down to a connectivity check between the initial state and the final states. Reject: PSPACE-Complete (search Universality problem).
Given a graph $G$, two vertices $s$ and $t$, and $c \in \mathbb{N}$. Does $G$ contain $4$ ($5$) edge disjoint paths of length at most $c$? For 4 paths the problem is solvable in polynomial time, for 5 paths it is NP-hard.
Given an edge-weighted graph $G$ and two vertices $s$ and $t$, what is the minimum (maximum) weight of a $s$-$t$ cut in $G$? See minimum-cut (polynomial) and maximum-cut (NP-hard).
Given a set of linear constraints, is there at least one (integral) point in their intersection? Solvable in polynomial-time if variables are not restricted to be integers, otherwise NP-hard.