How do nodes agree on timestamps? While re-calculating the difficulty every 2016 blocks, how do nodes agree on the new difficulty? There is no unique timestamp on the p2p  network, because nodes can lie about their time stamps. Let us say I calculated the new difficulty and found N, another person found N+3. How is the consensus about the new difficulty arises? The formula depends on the time elapsed for the last 2016 blocks, so without a consensus about time stamps, how do we arrive at a consensus about the new difficulty?
Block headers contain timestamps. Those timestamps cannot be changed without redoing the work on those blocks. If we have consensus about which chain has the most work, we also have consensus about what the next difficulty should be. Those timestamps might not be correct: you rightly note that a miner might lie about what timestamp a block was mined at. 

What mitigations does Bitcoin have against miners lying? If a block timestamp is before the median of the last 11 blocks, the block will be rejected. If a block timestamp is more than 2 hours later than the clock of the node validating the block, the block will be temporarily rejected.